The benefits are visible if you search for the word "TSX". It says:
"Replacing the insert and update functions of our specialized growing hash table with Intel TSX variants increases the throughput of our hash table by up to 7%"
Maybe it depends on what activities the ICC engages in within the US. Le Monde doesn’t have “jurisdiction” in the US (or anywhere) to arrest anyone, but they still do investigations, which are presumably still legal for foreign journalists in the US.
When I benchmarked that a few years ago, I found the overhead of a syscall made mmap much slower (assuming the C or C++ memory allocator had already received some memory from the OS it could dole out).
Does this apply to integer keys in the computational models that can do operations other than simple comparisons? In the transdichotomous model, I thought the best known sorting algorithms were O(n lg lg n) worst case, while the best known inversion counting models were Ω(n √ lg n), following “Counting Inversions, Offline Orthogonal Range Counting, and Related Problems”.
> why would I care about people coming from other countries? I mean, what do I get in return?
This is a pretty stunning question.
Most people care about people other than ourselves. Most people sometimes do things to benefit others, even if they don't "get in return", as you put it, and they expect others to behave similarly. For example:
1. A billion people base their religious beliefs on venerating the self-sacrifice of God dying and/or giving-His-only-begotten-son to help others.
2. Most people believe that people other than themselves can have subjective experiences of joy and pain. Most people would take a little time out of their day, for instance, to help an abandoned, injured infant, even if they would never "get anything in return" for their selfless act; even though the infant can't promise them anything in return or prove that they are suffering, people see a suffering child and feel a sort of basic level of empathy.
3. Almost everyone who has political opinions is arguing not primarily about themselves, but about people more vulnerable than them who are being hurt by existing policy or will be helped by new policy - usually large classes of people that the arguer will never meet.
4. The idea that other people matter is so incredibly common, we diagnose people who cannot experience it with a medical condition sometimes informally called "sociopathy"
So I'm going to assume you know that most people expect you to care about people other than yourself, and I'm going to assume that you actually do care about people other than yourself.
Now try to imagine what it would be like to extend that empathy to foreigners.
Assuming you ignore the constant. And if you're willing to ignore the constant, you can get O(c) access, O(N^(1/c)) insert and delete at arbitrary indices, and O(c) insert at head and tail, for any constant c. The trick is to make the array into a B-tree of width N^(1/c) and depth c. Note that the insert/delete time is amortized: the worst-case time is O(cN^(1/c)).
The instruction and instruction set referenced in the comment you're referring to (PCMPxSTRy and SSE) are not AVX512; they were introduced long before AVX512 chips were manufactured.
> Weight is a weaker condition, since you can construct a polynomial weight sequence that results in linear height.
I'd like to hear more. The varieties of weight-balanced trees I'm aware of all have logarithmic height.
> In general, height is the easiest thing to restrict, but doing so restricts dynamic performance optimizations - you can't use splay trees, for instance
Good point.
BTW, you might be interested in Bose et al.'s "De-amortizing Binary Search Trees" <https://arxiv.org/pdf/1111.1665.pdf>, shows how to keep height logarithmic with "essentially any Binary Search Tree" (their phrase).
"A preliminary version of this article is published in Proceedings of Workshop on Algorithms and Data Structures, WADS ’89, Ottawa. An independent article has also been presented by Galperin and Rivest at the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA."
The title should be corrected to "SPARK", not "Spark". It's used all caps each time it's mentioned on the page. That's also how I've seen this tool referred to elsewhere in the programming language literature: https://en.wikipedia.org/wiki/SPARK_(programming_language)
"Replacing the insert and update functions of our specialized growing hash table with Intel TSX variants increases the throughput of our hash table by up to 7%"