Comment by eru
2 days ago
If you are willing to sacrifice performance, you can implement dicts via linear lookup in much less code than a proper hash table.
2 days ago
If you are willing to sacrifice performance, you can implement dicts via linear lookup in much less code than a proper hash table.
It’s Python, you’ve already sacrificed performance, what a little bit more?
That's the spirit!
(Slightly less silly: the folks at https://github.com/faster-cpython are doing great work, too.)
Are they still? I thought this project was no longer really active.
1 reply →
Because Python dicts guarantee iteration order is the same as insertion order (https://docs.python.org/3.7/library/stdtypes.html#typesmappi...) Python dicts aren’t just proper hash tables.
Because of that it wouldn’t surprise me much if that sped up some standard benchmarks, for example ones parsing lots of small json objects into dictionaries.
I would be very surprised if my silly suggestion would speed up some standard benchmarks, because even if you do insertion only you have to do a linear probe to find duplicates.
The way Python guarantees to preserve insertion order is pretty clever and doesn't really cost you much at runtime. They pretty much only added this guarantee because it was basically free to offer given the implementation choices they already wanted to make for other reasons.
> because even if you do insertion only you have to do a linear probe to find duplicates.
Yes, but that is almost free for the first insert and need not be much work for the second and third. Also, that naive implementation will use less memory.
The kind of benchmark I was thinking of are the “large_random” and “Kostyra” ones from https://github.com/simdjson/json_benchmark_results that parse arrays of small objects with very short keys.
For such objects, as I said, it wouldn’t surprise me _much_ if the extremely naive implementation were faster.