HNHacker News
TopNewBestAskShowJobs

NovaX

288 karma · joined May 4, 2011

https://github.com/ben-manes
submissionscomments
NovaX··on How we upgraded PostgreSQL
You probably need to run ANALYZE to rebuild the statistics, as that doesn't happen automatically after an upgrade.
NovaX··on Constant Time LFU
Have you tried making it adaptive [1]? Using hill climbing with a decay rate has a nice impact to correct for LRU-biased workloads [2].

[1] https://dl.acm.org/doi/10.1145/3274808.3274816 [2] https://github.com/ben-manes/caffeine/wiki/Efficiency#adapti...

NovaX··on AdoptOpenJDK 8u265 Available
It is a method-scoped variable that is operated on under the reader's lock. Therefore the additional locking by StringBuffer is unnecessary and there is no negative impact by switching to StringBuilder.
NovaX··on Lockless Algorithms for Mere Mortals
The vast majority of STMs use lock-based transaction management. There are lock-free designs, but these tend to perform worse due to creating a lot of memory bus traffic. Unfortunately lock-free algorithms can easily perform worse than their lock-based counterparts. There are often simpler alternatives to reduce lock contention pitfalls on hot paths (like map reads), while still taking advantage of locking (like map writes).
NovaX··on Performance of modern Java on data-heavy workloads
It is a stretch to claim caching is fundamentally at odds with GC. It is more correct to say that LRU breaks the generational hypothesis, because it prioritizes new entries which take a long time to be evicted. However many workloads are frequency biased and these one-hit wonders degrade the hit rate. That is why you'll see more aggressive eviction in a modern policy, so you'll have better GC behavior and higher hit rates using something like Java's Caffeine library.
NovaX··on Static Analysis in GCC 10
In 2005.

https://lists.gnu.org/archive/html/emacs-devel/2015-02/msg00...

NovaX··on Static Analysis in GCC 10
They also refused Apple's offer to relicense LLVM to the GPL, contribute it to GCC, and assign copyright to FSF.
NovaX··on Generics in Go with Ian Lance Taylor (2019)
It isn't a problem if you design an API by following the rules (PECS). Use wildcards for method parameters when this is the desired behavior. It is not hard to do things right.

https://howtodoinjava.com/java/generics/java-generics-what-i...

NovaX··on Ristretto: A High Performance, Concurrent, Memory-Bound Go Cache
I am not familiar with the Go code, but in the Java version (Caffeine) this is handled by a per-entry state machine. The entry is written to the Map first and the policy work buffered for replaying. If the replay occurs out-of-order (e.g. context switch before appending causing removal=>add), then the entry's state guards against policy corruption. This may not be necessary in their case due to using a sampling policy and other differences.
NovaX··on Ristretto: A High Performance, Concurrent, Memory-Bound Go Cache
There is not a lot of research in this area and I briefly outlined my understanding of the current state when responding to a github issue:

https://github.com/ben-manes/caffeine/issues/345#issuecommen...

NovaX··on Cache Concurrency Control
It is very common and often referred to as jitter.

A variation, called scaled ttl, was nicely discussed in this video. https://www.youtube.com/watch?v=kxMKnx__uso

NovaX··on Russ Cox’s response to “Go Is Not a Community Driven Project”
I believe the author is referring to this post, https://web.archive.org/web/20181209143223/https://plus.goog...

Guava was always made available as Google's Java core utilities. I think it was always a misunderstanding to expect external contributions, like Apache Commons, as that was not its original intent. Rather it was to reduce internal duplication and ad hoc code with a shared standard. It then became useful for open-sourced Google projects (like API clients) and recruiting (new hires would be familiar with Google's libraries). Many suggestions are best spun off into new libraries, rather than donated to Google to maintain.

Java's many flaws have been papered over by a large ecosystem of libraries. As a non-gopher, I'm not sure if that same spirit exists. Perhaps that is due to the dependency debates, whereas Maven Central was quickly adopted when managing jars (via Ant) became too burdensome. Perhaps modules will help, as the language doesn't have to be batteries included.

NovaX··on Another ZFS Port on Linux
> The other issue would be "taming" the ARC

Has anyone considered replacing ARC? It actually has fairly poor hit rates compared to other policies, with very modest improvements over LRU. I also wonder how much ghost entries contribute to space overhead, which is actually trivial to remove (ARC is an adaptive SLRU - so replace ghosts with a sampling hill climber).

NovaX··on Thundering Herds and Promises
Guava cache's successor, Caffeine [1], handles the asynchronous case. In your scenario, you could set a timeout on the future as the entry will be discarded if the future results in an error.

[1] https://github.com/ben-manes/caffeine/wiki/Population

NovaX··on Google launches an end-to-end AI platform
We had 4-6 month cyclical code yellows. It's not unlike the game where 20% projects could only be within the same team without significant blowback. Things are only reasonable when used as designed, which is not how all of Google operates for everyone. You can talk in the general sense, but you cannot speak definitively especially when such actions are blessed by the executive team.
NovaX··on Google launches an end-to-end AI platform
There are many ways at Google to stop people from moving teams. For me it was a code yellow. I am hazy, but it was either referred to as indentured servitude or more politely stated as such by our senior director who expected 3 year stints. This was at MTV, probably a toxic environment due to CxO visibility.
NovaX··on Hashed and Hierarchical Timing Wheels: Data Structures for Timers (1987) [pdf]
It's also quite useful in caches, though still novel to do so:

http://highscalability.com/blog/2019/2/25/design-of-a-modern...

NovaX··on The State of Caching in Go
Zipf is a little idealistic. It is perfect for a quick analysis as the base case that a cache should excel at. Unfortunately LRU doesn't because it can be easily polluted. (examples: https://github.com/ben-manes/caffeine/wiki/Efficiency)

A database will often scan many records which would flush an LRU. Postgres uses small LRU buffer caches in your per-thread model, backed by a larger LRU-like cache. The buffer caches are easily flushed by scans, but protect the shared cache from this noise. That shared cache could probably benefit from a smarter policy and this is an on going topic.

NovaX··on Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
Yes, that would be fun. :)

For fixed expiration (e.g. 5 min TTL), I use time-bounded LRU queues. Then if the head item has not expired, its successors have not either. If it has, it is merely a poll.

For custom expiration (varies per-entry), I use a hierarchical timer wheel. This replaces sorting with hashing, with an amortized O(1) cost.

For refresh, that's when I do it on access since its being used. I keep a refresh timestamp and an expiration timestamp, so that a refresh can occur while the data is valid but aging, but a blocking load is required when its too stale (expired).

You might enjoy this slide deck of the ideas that I use: https://docs.google.com/presentation/d/1NlDxyXsUG1qlVHMl4vsU...

NovaX··on Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
That certainly helps, though you assume strict LRU vs approximate ARC. One can of course use similar schemes on LRU (like memcached does) or sampling LRU, making it approximate but reducing the lock contention. The technique that I've used is to buffer and replay events against the policy, so that reads are just a CAS into a ring buffer and replaying is under performed under a non-blocking lock. That works well with any policy and extends to other features, like expiration.
NovaX··on Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
Naming aside, the structure is <LRU | LFU filter | LRU>. The latest version of that is adaptive, where the front LRU may grow or shrink based on the workload. This allows the cache to mimic LRU for recency-skewed workloads (e.g. job queues) and LFU for frequency-skewed ones (e.g. loops). In a stress test, ARC and LIRS had 20% hit rate, Caffeine has 39.6%, and Optimal is 40.3%.

https://user-images.githubusercontent.com/378614/52891655-29...

NovaX··on Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
Can you explain how ARC can be more easily lock-free than LRU? ARC has to coordinate 4 doubly-linked lists and a pivot on every access.
NovaX··on Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
The LHD paper lacks a robust analysis against different workloads. The few traces they use are either private or not considered representative workloads. For MSR, the provider (SNIA) specifically states: "WARNING: These traces are over 10 years old! They should not be used for modern research!".

It would be much more interesting if they used the traces from ARC and LIRS, perhaps also UMass and Wikipedia. These traces are publically available and used by multiple papers from a variety of groups.

I have not seen a sampling-based policy that outperforms a policy that has tracks history outside of its working set. Since the examples specifically avoided that comparison, I suspect that it under performs in comparison. That isn't to say it isn't a useful advancement, but that a more robust analysis is needed to validate their claims.

NovaX··on Rust at speed – building a fast concurrent database [video]
That makes sense, thanks!

For microbenchmarks, I try to remove any overheads during runtime by precomputing. That means fully populating the map (only hits) and generating the distribution of keys. Then the threads start at a random index and increment for the key on each operation. This is a good example in Java, https://github.com/ben-manes/caffeine/blob/master/caffeine/s...

I would expect ~15-30ns per integer key lookup on a decent hashtable, w/o concurrency, at a modest size (few collisions). Using a concurrent map that supports lock-free reads doesn't have to be significantly different. Since hashtable design make such a big difference, it sounds like you've narrowed it down to that as a reasonable bottleneck. Thanks for investigating.

https://tessil.github.io/2016/08/29/benchmark-hopscotch-map....

NovaX··on Rust at speed – building a fast concurrent database [video]
Thanks for the reply. I wasn't trying to critique your work, but when something seems wrong it's worth trying to understand why. That's either a mistake in the project or my understanding.

Java and C++ concurrent maps scale reads quite well, both in practice and in research. I was comparing only in-memory read-only map lookups, not those that persist like FASTER and MassTree. I should note though that decade or older hardware will have lower multi-threaded throughput by using many slow cores (Azul, Sparc), so those raw numbers are not comparable to today's x86 machines.

In my experience when adding atomic writes to mostly uncontended fields during this lookup, the performance degrades to 33% of the raw map. Therefore 25M/s did not make sense and I believe there is a limiting factor that could be removed to increase throughput.

[1] https://preshing.com/20160201/new-concurrent-hash-maps-for-c...

[2] http://people.csail.mit.edu/shanir/publications/LazySkipList...

[3] https://arxiv.org/pdf/1809.04339.pdf

[4] https://dl.acm.org/citation.cfm?id=3210408&dl=ACM&coll=DL

[5] https://www.usenix.org/legacy/event/atc11/tech/final_files/T...

[6] https://web.stanford.edu/class/ee380/Abstracts/070221_LockFr...

[7] https://arxiv.org/pdf/1601.04017.pdf

NovaX··on Rust at speed – building a fast concurrent database [video]
The benchmark allocates a new ReadHandle on every get(key) operation, whose constructor performs work under a shared lock. This is a design flaw of the benchmark, not the library.
NovaX··on Rust at speed – building a fast concurrent database [video]
It is not lock-free. Every time he reads he acquires a lock by calling epochs.lock(). That may not explain the numbers entirely, but this benchmark is completely bogus.
NovaX··on Rust at speed – building a fast concurrent database [video]
His chart is very wrong: https://github.com/jonhoo/rust-evmap/blob/master/benchmark/r...

Both Zipf (skewed) and Uniform distributions have the same read throughput. That would not occur because of hardware caches and memory effects. A Zipf means that some entries are read much, much more often (80/20 rule, hot/cold cache entries). The hardware caches should benefit from this and that is how you get superlinear effects.

A uniform is the same as a random access, e.g. all eviction policies would degrade to random replacement as there is no recency/frequency/locality benefits. This means if the dataset cannot reside entirely within the CPU cache then we should see a different throughput. Yet, they are the same.

His benchmarks only have 10k elements so maybe it all fits in the cpu cache. If that's true then 25M/s is absolutely awful. Something is wrong.

NovaX··on Rust at speed – building a fast concurrent database [video]
He was showing a microbenchmark of docs.rs/evmap and not of Nora. This is a load test on the local machine: https://github.com/jonhoo/rust-evmap/tree/master/benchmark

His read throughput is linear to the number of cores, which means that it must have been run with the same number of cores to threads. Otherwise context switching and sharing of cores would have resulted in sublinear growth (you can get superlinear growth, but it won't look like that). Assuming his numbers are not fake, his github charts indicate a 32+ core machine.

My 2015 benchmarks were on a Azure G4, Xeon E5-2698B v3 @ 2.00GHz (16 core, hyperthreading disabled), 224 GB, Ubuntu 15.04. They show a slight superlinear growth for reads (Caffeine). https://github.com/ben-manes/caffeine/wiki/Benchmarks#server...

Both benchmarks use a Zipf distribution. I believe he said it only supports single-writer semantics, whereas mine is roughly per-entry (per hashbin). So reads should be safe to compare, and we can ignore his slow write rate. His should be faster as I do more work to maintain complex eviction policies, whereas his can reading a pseudo-immutable map with no eviction.

Since he does not perform any cache operations, as it is a concurrent map, we should be comparing against another unbounded concurrent map. That is over 1 billion reads per second on the above hardware. That is why I think something is miserably wrong or I'm misunderstanding something fundamental. Achieve 25M/s is a very disappointing result.

NovaX··on Rust at speed – building a fast concurrent database [video]
I’m confused by the read/write performance numbers. I don’t disagree that lock-free reads are better, but 25M reads/sec at 16 threads is really bad. I can do 13.5M with a niave exclusive lock on an Lru cache, and 380M reads / 48M writes on a concurrent cache. The left/right concurrency isn’t novel and I feel bad being so very underwhelmed. What am I missing?
← PreviousPage 4 of 6Next →