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

Properly testing concurrent data structures

matklad.github.io

Post reply on HN
Print view View original

21–30 of 33 posts

Re: Properly testing concurrent data structures

#21

Post by moonchild »

o11c wrote: post #14

If I understand this correctly, this approach has limitations regarding soft forward-progress guarantees. Consider a cmpxchg loop where the body computation is not quite trivial, but on real hardware (and with real schedulers) is exceedingly unlikely to be interrupted on a given CPU. Thus, if `n` is the number of CPUs, it has a worst-case `1/n` chance of making progress. But with this testing approach, it instead has…

> 1/t^p

i don't think that's right. it's just 1/t. after all, after t time, one task must have made progress; since there are t tasks, the probability that i'm the task that made progress is just 1/t

the primary point of confusion, i think, is that getting interrupted does not mean that you are necessarily going to lose the cas

Re: Properly testing concurrent data structures

#22

Post by JonChesterfield »

int08h wrote: post #16
idle_cycles wrote: post #2

This is great, is there a "loom" like library for C++? I have a set of lock-free data structures that I would like to test.

Yes, the (IMHO) the easiest one to use is the Relacy Race Detector ( https://github.com/dvyukov/relacy and https://www.1024cores.net/home/relacy-race-detector ) It's been around a while and is easy to work with. Written by Dmitry Vyukov, an expert in the concurrency world.

Relacy is notable for being the only one in c++ that knows what a fence is, at least last time I looked.

It told me a structure might not make forward progress on some thread interleaving. I.e. if only one thread ever runs, the others don't do anything. That's true but uninformative. I wasn't able to coax it into using a vaguely fair scheduler to get more useful information out than that.

Re: Properly testing concurrent data structures

#23

Post by zokier »

I suppose if you want to be really thorough, you could run the tests with ptrace and single-step the threads to make different interleavings at instruction level. Has anyone seen that sort of thing done? Is there any alternatives for black-box testing, if you are not able to instrument the code like what is done here?

Re: Properly testing concurrent data structures

#24

Post by scottlamb »

zokier wrote: post #23

I suppose if you want to be really thorough, you could run the tests with ptrace and single-step the threads to make different interleavings at instruction level. Has anyone seen that sort of thing done? Is there any alternatives for black-box testing, if you are not able to instrument the code like what is done here?

I've done that for testing async signal handlers, but the combinatorics are much more favorable there. If the base thread runs n instructions, you just need n runs through that run 0..n instructions before inserting the signal, and then the signal handler runs to completion and then so does the base thread. O(n^2) total time. But with t threads each with n instructions to run, and they can interrupt each other at any boundary...it's not approachable for reasonable values of n. You need to reduce by singling out the operations with interesting behavior and simulating, I think.

Re: Properly testing concurrent data structures

#25

Post by zbentley »

oasisaimlessly wrote: post #18
claytonwramsey wrote: post #13

Earlier quoted context omitted.

It would be convenient to use async, but the other requirement is that we don’t want to change the outwardly-observable API of the software under test. Since async is “infectious,” we have to use sync implementations for sync APIs.

What about stackful coroutines? They don't necessarily change the API.

Why does stackfulness not color functions? So long as preemption/parallelism boundaries are manually annotated, I don’t think stackful coroutines save you anything here.

Re: Properly testing concurrent data structures

#26

Post by LegNeato »

oasisaimlessly wrote: post #18
claytonwramsey wrote: post #13

Earlier quoted context omitted.

It would be convenient to use async, but the other requirement is that we don’t want to change the outwardly-observable API of the software under test. Since async is “infectious,” we have to use sync implementations for sync APIs.

What about stackful coroutines? They don't necessarily change the API.

Check out https://github.com/jonnadal/fibril

Re: Properly testing concurrent data structures

#28

Post by anonymoushn »

zbentley wrote: post #25
oasisaimlessly wrote: post #18

Earlier quoted context omitted.

What about stackful coroutines? They don't necessarily change the API.

Why does stackfulness not color functions? So long as preemption/parallelism boundaries are manually annotated, I don’t think stackful coroutines save you anything here.

Just don't annotate them? The design of async is a wound that can be bandaged by dumping all your registers on the stack and jumping.

Re: Properly testing concurrent data structures

#29

Post by thrwyexecbrain »

One downside of this approach is that the tested code itself has to be modified to accomodate the testing code.

I think the same could be achieved by launching two threads and single stepping them with ptrace to "randomly" interleave the execution of their instructions. Something like rr's chaos mode.

Some instructions may not be atomic though, so we would need a way to single step on "atomic microcodes" if that's even possible without emulation?

Re: Properly testing concurrent data structures

#30

Post by a_t48 »

int08h wrote: post #16
idle_cycles wrote: post #2

This is great, is there a "loom" like library for C++? I have a set of lock-free data structures that I would like to test.

Yes, the (IMHO) the easiest one to use is the Relacy Race Detector ( https://github.com/dvyukov/relacy and https://www.1024cores.net/home/relacy-race-detector ) It's been around a while and is easy to work with. Written by Dmitry Vyukov, an expert in the concurrency world.

32 bit only, no clang support :(
Post reply on HN