OpenDream icon indicating copy to clipboard operation
OpenDream copied to clipboard

DreamList membership reverse lookup

Open Ruzihm opened this issue 2 months ago • 3 comments

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.

Ruzihm avatar Dec 14 '25 21:12 Ruzihm