A young computer scientist and two colleagues show that searches within data structures called hash tables can be much faster than previously deemed possible.
-
-
-
I also trust the legitimacy of the discovery. There's a lot of fake 'discovery' articles out there.
-
-
-
Infrastructural APIs are much slower to change, and in a lot of cases the use of those APIs are dependent on a specific version. The change will definitely occur over time as the practical limitations are discovered
-
-
This is the paper the article is about: https://arxiv.org/pdf/2501.02305
-
Also never even start optimizing until you profile and are sure the bit you are trying to optimize even matters to the overall performance of your program.
-
Using bencode over json would probably speed up the web more. Not to mention good ole X.690. The web is completely cooked when it comes to efficiency.
-
-
-
-
I've only used java but java hash tables are stupid fast in my experience, like everything else in my crap programs was 1000 times slower than the hash table access or storage.
-
The paper was published by IEEE and with professors as co-authors. Only the second author is a student. And I wouldn't dismiss it out of hand like that because of a magazine article. Students come up with breakthroughs all the time.
The paper itself says it disproves Yao's conjecture. I personally plan to implement and benchmark this because the results seem so good. It could be another fibonacci heap situation, but maybe not. Hash tables are so widely used, that it might even be worthwhile to make special hardware to use this on servers, if our current computer architecture is only thing that holds back the performance.Edit: author sequence
-
And yet all that pales in comparison to using react (or whatever framework) over vanilla js. Enter McMaster-Carr.
-
yupyup, just send HTML over the wire. it's fine.
-
Hash trees are super efficient when they're not nearly full. So the standard trick is just to resize them when they're too close to capacity.
The new approach is probably only going to be useful in highly memory constrained applications, where resizing isn't an option.
-
Depends on the implementation, but most will, yes. There are other forms of associative arrays, like trie or binary tree, but hash is the most common.
-
JSON libraries are stupidly well optimized. There are binary encoding schemes that are faster and more compact, but its hard to beat JSON for text-based.
