cfengine/core — pull request #912 by lpefferkorn (2013-08-29 22:17:49+00:00)
Title: Redmine #1875: Locks - Replace global Item list by a local Red Black Tree

Regarding the test case provided by Neil in Redmine #1875 https://cfengine.com/dev/issues/1875#note-16 , I have found that the use of an Item list is costly, especially IsItemIn() which scans linearly all the list entries at each call.

Using the internal RB Tree data structure instead helps to speedup the process:

Before:

$ time ~/tmp/cfe-master/bin/cf-agent -Kf /home/loic/.cfagent/inputs/bug1875.cf -D sizes8200
2013-08-29T23:58:42+0200 notice: R: List size => 8200

real	0m12.195s
user	0m12.030s
sys	0m0.053s

After:

$ time ~/tmp/cfe-master/bin/cf-agent -Kf /home/loic/.cfagent/inputs/bug1875.cf -D sizes8200
2013-08-29T23:54:19+0200 notice: R: List size => 8200

real	0m5.131s
user	0m4.953s
sys	0m0.073s

I don't see any immediate drawback to this change, since DONELIST was not used elsewhere.
What's your opinion ?