Comment by eru
10 hours ago
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.