jbapple

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”.

See also https://web.archive.org/web/20190927163255/http://cantorsatt...

> 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.

That's it. That's the whole trick.

Good luck!

Got it; thanks for explaining.

I suppose in a microecon 101 model, there’s some elasticity that causes the cost of the fees to be borne partially by the merchants?

Can you explain more?

> Has anyone explored regexp minimization?

There has been significant work on https://en.wikipedia.org/wiki/DFA_minimization

It's a deterministic attack vector, so significant offline computation prep work is not unusual.

https://en.wikipedia.org/wiki/Algorithmic_complexity_attack

https://www.freecodecamp.org/news/hash-table-attack-8e4371fc...

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)).

Where can I read more about the decision to develop Lean 4 in private, and what is the status of https://github.com/leanprover/lean4, in your view?

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).

These trees nearly identical to Scapegoat Trees, which were a rediscovery of the idea by different authors. https://cglab.ca/~morin/teaching/5408/refs/a99.pdf has the history:

"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."

But logit-weight trees have logarithmic height, yes?

Are you familiar with hybrid logical time systems like " HybridTime - Accessible Global Consistency with High Clock Uncertainty" (http://users.ece.utexas.edu/~garg/pdslab/david/hybrid-time-t...) or "Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases" (https://cse.buffalo.edu/tech-reports/2014-04.pdf)? I'd be interested in reading what you view as the tradeoffs between Bloom clocks and these systems.

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)

> portfolio theory means that serious due diligence isn't worth the effort.

Could you expand on this?

What do you mean by "Zig is optimal"?

The indexes themselves might underperform an index+VC strategy though if they don't have access to high-growth companies that are staying private.

Even if investors shouldn't pick stocks, it might be wise for them to invest in an index of companies that they are now prevented from investing in.

Over a 40-year career, assuming 4% real capital growth after inflation and a 3% safe withdrawal rate in retirement, a worker has to invest 25% of their gross income every year to have the same net income in retirement (assuming identical taxation rates).

The median annual household income in the US is around $60k.

Second Google hit when searching for the paper title:

https://www.cs.vu.nl/~herbertb/papers/osreview2008-2.pdf

> Hmm I’m seeing the opposite. The last graph shows Google’s hash table outperforming in all but a few places, including at 400k.

You're exactly right, General Pizza. I was trying to say that the Google table was faster, even though the author claimed that his or her table was "fastest" without qualification.

Thanks for pointing that out; I'll leave my post as it is so yours continues to make sense in context.

This post has some overconfident and under-researched claims:

> This came about because last year I wrote the fastest hash table (I still make that claim)

I'm extremely dubious of claims of the "fastest $DATA_STRUCTURE" without qualifiers about workload, hardware, and time/space trade-off. In particular, the last graph of this post shows some workloads (400k int keys, int[16] values, unsuccessful lookups) where the author's implementation of Swiss Table (as Google called their table) is 3x-10x slower than "bytell_hash_map", the author's own design.

> google_flat16_hash_map. This last one is my implementation of Google’s new hash table. Google hasn’t open-sourced their hash table yet, so I had to implement their hash table myself. I’m 95% sure that I got their performance right.

The talk announcing Swiss Table clearly didn't have enough detail to fully replicate their results. This 95% claim is rather astonishing in light of that.

That's the same as Tableau's HyPer. From the page you linked to:

"The commercial license for HyPer, a spin-off of TUM, has been acquired by Tableau Software"

FWIW, Impala compiles more than just predicates. See, for instance, https://github.com/apache/impala/blob/e98d2f1c0af270930cd8a5...

Are either of these specifically adaptive packed-memory arrays? The former cites it, but only has one type of PMA implemented, it seems.

> I'm not sure I understand your question.

I'm asking for a citation.

> 95% of any increases in FICA taxes are paid for by employees (via adjustments to wages and salaries)

What evidence indicates it's 95% and not 20% or 80% or 99%?