Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A collection of lock-free data structures written in standard C++11

github.com

Post reply on HN
Print view View original

81–86 of 86 posts

Re: A collection of lock-free data structures written in standard C++11

#81

Post by CyberDildonics »

gpderetta wrote: post #65
CyberDildonics wrote: post #58

Earlier quoted context omitted.

> Good lock free algorithms use double-width instructions like cmpxchg16b which compare 64-bits but swap 128-bits The instructions should compare 128 bits and swap 128 bits. I don't know why 'good' algorithms would use these if they don't need to, because 128 bit operations are slower. Not only that, 128 bit compare and swap doesn't work if it is not 128 bit aligned while 64 bit compare and swap will work even if the…

On x86, any CAS on a misaligned address that crosses a cache line boundary can fault in the best case (if the mis-feature is disabled by the os) or cost thousands of clock cycles on all cores. So it "works" only for small values of "works".

That's over a cache line boundary, but 128 bit don't even work when they are unaligned, so you can't do things like swap two pointers, then move down 64 bits and swap two more pointers.

Re: A collection of lock-free data structures written in standard C++11

#83

Post by m4nu3l »

ot wrote: post #73
m4nu3l wrote: post #71

Earlier quoted context omitted.

What can cause the mutex to lose track of the number of waiters?

Generally you have a small number of bits to count the waiters, because the mutex state has to be a word you can CAS and so you have either 32 or 64 bits to pack all the state you need. If your counter saturates you lose track of the waiters, and you have to fallback somehow.

Makes sense, thanks for the explanation!

Re: A collection of lock-free data structures written in standard C++11

#84

Post by josephg »

kerkeslager wrote: post #61
bluGill wrote: post #49

Earlier quoted context omitted.

This is impossible to do in a useful way for publication. You can do case studies, but minor changes in various factors that seem minor can make a massive difference in benchmarks. As such you need to find real world data, used in a real world scenario, for your application: then benchmark it. Even then you have a benchmark useful for your application only, and not worth publishing.

I disagree. I've gotten a lot from reading publications about people profiling their applications and posting about the results with descriptions of their application design and load. Yes, obviously you can't read that and draw conclusions about how the same data structure or algorithm will perform in your application, but it helps you build an intuition for what is likely to work in applications with different chara…

Thanks for the link! I read that about a decade ago, and its still a great read. That article makes it seem ridiculous to implement software any other way.

And yet, yesterday I watched a talk about how ridiculous it is to use mmap to implement a database:

https://db.cs.cmu.edu/mmap-cidr2022/

And I ended up side tracked watching some talks from CMU about database page buffers and such.

Its weird how people with different backgrounds (OS / kernel people and database people) come to very similar problems in computing with very different perspectives, and they end up implementing very different systems as a result. And in each case, each community thinks the other way is basically wrong.

My understanding is that Linus Torvalds thinks O_DIRECT is a ridiculous flag that database people probably don't want. And from a database perspective, its crazy how difficult the linux kernel makes it to write high performance filesystem code that never corrupts data if the system crashes. fsync is a misshapen sledgehammer, and disk write barriers or IO completion events are totally missing from linux.

Re: A collection of lock-free data structures written in standard C++11

#85

Post by gpderetta »

dragontamer wrote: post #66
gpderetta wrote: post #63

Earlier quoted context omitted.

Indeed L3 being shared and also often working as the MOESI directory works out to the interthread latency being the same order of magnitude as the L3 latency. My point is that sync has nothing to do with caches. Caches are coherent all the time and do not need barriers. In particular I don't think the git pull/push maps well to MOESI as it is an optimistic protocol and only require transfering opportunistically on de…

> The explicit sync model is more representative of non coherent caches, which are not really common as they are hard to use. Not that I'm a professional GPU programmer. But I'm pretty certain that GPU caches are non-coherent. But yeah, cache-coherence is just assumed on modern CPUs. Your clarification on store-queues and load-queues is helpful (even if the caches are coherent, the store-queue and load-queue can stil…

> Not that I'm a professional GPU programmer. But I'm pretty certain that GPU caches are non-coherent.

Yes, I was specifically referring to general purpose CPUs; I'm quite unfamiliar with GPUs, but I don't think anybody has ever accused them of being easy to program. Also I understand that GPUs (and CPU-GPU links) is an area where remote atomics already exist.

> So it sounds like your point is that the various sync() instructions are more about these queues?

for the most part yes, specifically fences enforce ordering on any operation that can execute out of order (even on in-order CPUs memory ops can be reordered), but only up to the coherence layer (i.e. L1). Ordering from the coherence layer on is enforced by the coherence protocol. You could of course have a model where fences are needed for for global coherence, but it would be too slow (having to flush the whole cache), too hard to use (as you would need to specify which lines need to be sync'd) or both.

You could see something like the store buffer as a non-coherent cache (as reads can be fulfilled form it), with fences restoring the coherence, but I don't think it is a terribly useful model.

Re: A collection of lock-free data structures written in standard C++11

#86

Post by kazinator »

kerkeslager wrote: post #59
ot wrote: post #9

Earlier quoted context omitted.

This is true in principle and it is good calling it out, but in practice I've never seen a mutex-based data structure beat an equivalent lock-free data structure, even at low contention, unless the latter is extremely contrived. A mutex transaction generally requires 2 fences, one on lock and one on unlock. The one on unlock would not be strictly necessary in principle (on x86 archs the implicit acquire-release seman…

I appreciate your polite tone here. To expand on this at the risk of sounding a bit rude: nobody should listen to anyone who speaks about performance in terms of reasoning about a system instead of profiling it. Computers are shockingly complex. I can't tell you how many times I've reasoned about a system, ran the profiler, and discovered I was completely wrong. When I was working on an interpreter for a Lisp, I impl…

Optimizing Lisp lexical environments with hashes is going to be a fool's errand. The way you optimize lexical environments is by compiling them, so that there is no searching at all.

The value in the interpreter is that it provides an alternative implementation of the semantics. This becomes particularly valuable in some area that happens to be under-documented, and the compiler and interpreter are found to disagree.

It can be easier to get the semantics right in the interpreter. A simple implementation of environments (and whatnot) reduces the likelihood of bugs and leaves the code readable. Interpreted behavior of special forms can usually serve as the reference implementation for compilation.

If an interpreter is slow, that just means that the build steps for bootstrapping the compiler using the interpreter takes longer.

Post reply on HN