DreamList membership reverse lookup
This PR expands on the work done by @redmoogle in #2418 in speeding up dreamlist ContainsValue by adding a reverse lookup for list membership checking.
It comes with a logic fix, some overriding of contains in child classes of DreamList which don't keep the lookup synchronized, and an alist fix to support alist += 1 at runtime which was run into during testing.
I agree with @wixoaGit that a proper fix for #2367 will involve changing Equals and a new GC but I do notice that caching membership in this way substantially speeds up the in operator for code which makes frequent checks for list membership with in, exceeding the speed of byond's list implementation. So I wonder if it is worth including anyway.
I tested performance changes with the following verb. Alist was included as point of comparison, its performance should not be affected by changes. Although I did notice that a change was needed to support alist += 1 and that is in this PR too. I can submit that as a separate PR if this one doesn't go anywhere but it was needed here for the comparison
verb/test_alert()
var/list/bigList1 = new()
for (var/i in 1 to 50000)
bigList1.Add(i*2)
var/start1 = world.timeofday
var/x = 0
for (var/i in 1 to 100000)
if (i in bigList1)
x += 1
world.log << world.timeofday - start1
world.log << "[x] should be 50000"
var/bigList2[0]
for (var/i in 1 to 50000)
var/datum/ind = new()
bigList2[ind] = i*2
var/start2 = world.timeofday
x = 0
for (var/i in 1 to 100000)
if (i in bigList2)
x += 1
world.log << world.timeofday - start2
world.log << "[x] should be 0"
var/alist/bigList3 = new()
for (var/i in 1 to 50000)
bigList3 += i*2
var/start3 = world.timeofday
x = 0
for (var/i in 1 to 100000)
if (i in bigList3)
x += 1
world.log << world.timeofday - start3
world.log << "[x] should be 50000"
Results Byond:
33
50000 should be 50000
42
0 should be 0
0
50000 should be 50000
Results OD before changes:
[INFO] world.log: 52
[INFO] world.log: 50000 should be 50000
[INFO] world.log: 37
[INFO] world.log: 0 should be 0
[INFO] world.log: 0
[INFO] world.log: 50000 should be 50000
Results OD after changes:
[INFO] world.log: 0
[INFO] world.log: 50000 should be 50000
[INFO] world.log: 0
[INFO] world.log: 0 should be 0
[INFO] world.log: 0
[INFO] world.log: 50000 should be 50000
This was a pretty "optimistic" test and doesn't really examine what overhead might be introduced by this PR so I'm curious if anyone can recommend a good way to test that.