model-checker-benchmarks.git
9 years agobench: add linuxrwlocks to benchmark runs
Brian Norris [Sat, 3 Nov 2012 01:44:07 +0000 (18:44 -0700)]
bench: add linuxrwlocks to benchmark runs

9 years agolinuxrwlocks: add linux locks test
Brian Norris [Sat, 3 Nov 2012 01:41:30 +0000 (18:41 -0700)]
linuxrwlocks: add linux locks test

9 years agounrelacy: define the relacy ASSERT macros, fixup rl::var
Brian Norris [Sat, 3 Nov 2012 01:19:34 +0000 (18:19 -0700)]
unrelacy: define the relacy ASSERT macros, fixup rl::var

9 years agobench.sh: change max-reads=2, log to directory
Brian Norris [Sat, 3 Nov 2012 00:39:20 +0000 (17:39 -0700)]
bench.sh: change max-reads=2, log to directory

Pass '-m 2' argument to the model-checker

bench.sh sends all logs to a date-named directory now

9 years agobench.sh: add test script for running benchmarks
Brian Norris [Fri, 2 Nov 2012 23:27:12 +0000 (16:27 -0700)]
bench.sh: add test script for running benchmarks

9 years agompmc-queue: expand to 2R2W, 2R1W, 1R2W tests
Brian Norris [Fri, 2 Nov 2012 23:23:10 +0000 (16:23 -0700)]
mpmc-queue: expand to 2R2W, 2R1W, 1R2W tests

I rewrote the test to allow a configurable number of readers and
writers, but then I figured out that our model-checker doesn't support
optarg() and its global optind properly, when using mmap()/mprotect()
snapshotting (it doesn't add the optarg library to be snapshotted...)

So, this test grows to 3 separate source files, at least for now. The
only change is the number of reader and writer threads.

9 years agobarrier: modify to allow more than one reader
Brian Norris [Fri, 2 Nov 2012 04:57:22 +0000 (21:57 -0700)]
barrier: modify to allow more than one reader

Just change the NUMREADERS macro to add more reader-threads.

Having 3 or more threads is a more interesting example, since there's
no contention if you just have one thread spin, waiting for the other.

9 years agompmc-queue: run more producer/consumer threads
Brian Norris [Thu, 1 Nov 2012 19:22:56 +0000 (12:22 -0700)]
mpmc-queue: run more producer/consumer threads

9 years agomcs-lock: add more locking tests to driver
Brian Norris [Thu, 1 Nov 2012 19:21:22 +0000 (12:21 -0700)]
mcs-lock: add more locking tests to driver

9 years agompmc-queue: improve driver, to read all items from queue
Brian Norris [Thu, 1 Nov 2012 19:19:58 +0000 (12:19 -0700)]
mpmc-queue: improve driver, to read all items from queue

threadB() will now read all currently available items from the queue.

9 years agobenchmarks.mk: -rdynamic is used for linking
Brian Norris [Thu, 1 Nov 2012 19:18:28 +0000 (12:18 -0700)]
benchmarks.mk: -rdynamic is used for linking

9 years agospsc-queue: don't statically construct the queue
Brian Norris [Fri, 12 Oct 2012 17:44:58 +0000 (10:44 -0700)]
spsc-queue: don't statically construct the queue

Our model-checker doesn't support constructors which perform
model-checking actions (e.g, atomic initialization) at load time (e.g.,
in a static execution of the constructor), since this happens before the
model-check object is created. Maybe we'll fix that in the future, but
for now, don't construct the queue at load time.

9 years agospsc-queue: compilable
Brian Norris [Fri, 12 Oct 2012 17:44:01 +0000 (10:44 -0700)]
spsc-queue: compilable

9 years agobenchmarks.mk: don't include base model-checker dir
Brian Norris [Fri, 12 Oct 2012 00:09:18 +0000 (17:09 -0700)]
benchmarks.mk: don't include base model-checker dir

All model-checker headers needed for user-program compilation should be
in $(BASE)/include now, not in $(BASE)/

9 years agospsc-queue: add Makefile, .gitignore
Brian Norris [Thu, 11 Oct 2012 23:45:39 +0000 (16:45 -0700)]
spsc-queue: add Makefile, .gitignore

9 years agowilliams-queue: fixup header
Brian Norris [Thu, 11 Oct 2012 23:40:05 +0000 (16:40 -0700)]
williams-queue: fixup header

Move the constructor lower, so that member definitions appear earlier
than it in the class definition.

Also, don't assign to members of the atomic structure directly; use a
temporary struct then assign the whole struct.

Still won't compile. Seeing linker errors, probably due to the fact that
this code uses a nonstandrad atomic template:
    std::atomic<counted_node_ptr>

Where counted_node_ptr is a struct with int and pointer members. Thus,
it has size of at least 96 bytes (32+64) and so probably isn't really
supported by atomics... I'm not sure where the author came up with this.

    $ g++ williams-queue.cc --std=c++0x
    /tmp/ccPQgiJC.o: In function `lock_free_queue<int>::lock_free_queue()': williams-queue.cc:(.text._ZN15lock_free_queueIiEC2Ev[_ZN15lock_free_queueIiEC5Ev]+0x92): undefined reference to `std::atomic<lock_free_queue<int>::counted_node_ptr>::load(std::memory_order) const'
    ...
    collect2: ld returned 1 exit status

9 years agowilliams-queue: add driver, Makefile, etc.
Brian Norris [Thu, 11 Oct 2012 23:37:37 +0000 (16:37 -0700)]
williams-queue: add driver, Makefile, etc.

Still doesn't quite compile. I'm mostly attempting compilation with a
C++0x compiler (G++ 4.6) for now, a la:

  g++ -o williams-queue williams-queue.cc --std=c++0x

9 years agowilliams-queue: trim excess implementation
Brian Norris [Thu, 11 Oct 2012 23:05:29 +0000 (16:05 -0700)]
williams-queue: trim excess implementation

Trim down to a single implementation. Still doesn't compile correctly.

9 years agowilliams-queue: add lock-free-queue
Brian Norris [Thu, 11 Oct 2012 18:31:03 +0000 (11:31 -0700)]
williams-queue: add lock-free-queue

Lock-free queue code from "C++ Concurrency in Action: Practical
Multithreading", by Anthony Williams

Code taken from:
  http://www.manning.com/williams/CCiA_SourceCode.zip
  http://www.manning.com/williams/

Note that this commit includes several implementation of pieces of the
queue. I will trim them down to a working class in the next step.

9 years agospsc-queue: use std::condition_variable
Brian Norris [Thu, 11 Oct 2012 18:24:11 +0000 (11:24 -0700)]
spsc-queue: use std::condition_variable

Model-checker doesn't support <condition_variable> header yet.

9 years agomcs-lock: driver bugfix (deadlocking)
Brian Norris [Thu, 11 Oct 2012 01:33:27 +0000 (18:33 -0700)]
mcs-lock: driver bugfix (deadlocking)

I didn't notice that the guard automatically locks/unlocks the mutex on
creation/destruction, respectively.

9 years agospsc-queue: fixup atomics, mutexes, threads
Brian Norris [Thu, 11 Oct 2012 01:03:37 +0000 (18:03 -0700)]
spsc-queue: fixup atomics, mutexes, threads

9 years agospsc-queue: unrelacy
Brian Norris [Thu, 11 Oct 2012 00:14:52 +0000 (17:14 -0700)]
spsc-queue: unrelacy

9 years agounrelacy: fixup header
Brian Norris [Thu, 11 Oct 2012 00:13:16 +0000 (17:13 -0700)]
unrelacy: fixup header

9 years agospsc-queue: add new benchmark
Brian Norris [Thu, 11 Oct 2012 00:03:04 +0000 (17:03 -0700)]
spsc-queue: add new benchmark

From:
https://groups.google.com/forum/?fromgroups=#!msg/comp.programming.threads/nSSFT9vKEe0/7eD3ioDg6nEJ

9 years agompmc-queue: driver fixes
Brian Norris [Wed, 10 Oct 2012 23:15:56 +0000 (16:15 -0700)]
mpmc-queue: driver fixes

* Initialize queue with at least one item

* Instrument some racy accesses in driver

* Print a little information to see what kind of loops we're stuck in

9 years agompmc-queue: add top-level Makefile
Brian Norris [Wed, 10 Oct 2012 22:50:48 +0000 (15:50 -0700)]
mpmc-queue: add top-level Makefile

9 years agofixup makefiles
Brian Norris [Wed, 10 Oct 2012 22:41:51 +0000 (15:41 -0700)]
fixup makefiles

9 years agobenchmarks: revert back to strong/weak compare-exchange
Brian Norris [Wed, 10 Oct 2012 22:20:17 +0000 (15:20 -0700)]
benchmarks: revert back to strong/weak compare-exchange

I fixed up the model-checker header, so these will compile.

9 years agompmc-queue: add test driver, Makefile, .gitignore
Brian Norris [Wed, 10 Oct 2012 21:25:33 +0000 (14:25 -0700)]
mpmc-queue: add test driver, Makefile, .gitignore

9 years agompmc-queue: fixup compilation
Brian Norris [Wed, 10 Oct 2012 21:22:26 +0000 (14:22 -0700)]
mpmc-queue: fixup compilation

* Remove "nonatomic" type template
* Don't use atomic<T>(T) constructor
* Don't use compare_exchange_weak()

9 years agompmc-queue: unrelacy
Brian Norris [Wed, 10 Oct 2012 20:59:35 +0000 (13:59 -0700)]
mpmc-queue: unrelacy

9 years agompmc-queue: add MPMC queue header
Brian Norris [Wed, 10 Oct 2012 20:54:56 +0000 (13:54 -0700)]
mpmc-queue: add MPMC queue header

From first example at:
http://cbloomrants.blogspot.com/2011/07/07-30-11-look-at-some-bounded-queues.html

9 years agomcs-lock: write proper driver
Brian Norris [Wed, 10 Oct 2012 18:11:55 +0000 (11:11 -0700)]
mcs-lock: write proper driver

9 years agomcs-lock: bugfix - didn't allocate mcs_mutex
Brian Norris [Wed, 10 Oct 2012 02:08:01 +0000 (19:08 -0700)]
mcs-lock: bugfix - didn't allocate mcs_mutex

This is a bug in the stupid driver I wrote (i.e., my fault). I was
struggling with the syntax, so I forgot to even initialize my objects.

9 years agoadd run.sh simple run script
Brian Norris [Wed, 10 Oct 2012 01:41:58 +0000 (18:41 -0700)]
add run.sh simple run script

9 years ago.gitignore
Brian Norris [Wed, 10 Oct 2012 01:41:00 +0000 (18:41 -0700)]
.gitignore

9 years agomcs-lock: add trivial driver, link with build system
Brian Norris [Wed, 10 Oct 2012 01:09:20 +0000 (18:09 -0700)]
mcs-lock: add trivial driver, link with build system

This benchmark doesn't do much yet.

9 years agomcs-lock: fixup Relacy code
Brian Norris [Wed, 10 Oct 2012 01:08:12 +0000 (18:08 -0700)]
mcs-lock: fixup Relacy code

Also, switch out 'compare_exchange_strong()' for 'compare_exchange()',
since we don't support the _strong syntax right now.

9 years agounrelacy: add some helpers for cleaning up relacy code
Brian Norris [Wed, 10 Oct 2012 01:05:33 +0000 (18:05 -0700)]
unrelacy: add some helpers for cleaning up relacy code

Relacy still uses a few things that I can't easily add, like a ()
operator for std::atomic<T>. We'll still have to replace some things by
hand in test cases written for Relacy.

9 years agomcs_lock: add mcs mutex
Brian Norris [Wed, 10 Oct 2012 00:13:47 +0000 (17:13 -0700)]
mcs_lock: add mcs mutex

From:
http://cbloomrants.blogspot.com/2011/07/07-18-11-mcs-list-based-lock_18.html

9 years agoadd top-level Makefile
Brian Norris [Tue, 9 Oct 2012 23:24:25 +0000 (16:24 -0700)]
add top-level Makefile

9 years agobarrier: add .gitignore
Brian Norris [Tue, 9 Oct 2012 23:24:16 +0000 (16:24 -0700)]
barrier: add .gitignore

9 years agobarrier: add test driver, Makefile
Brian Norris [Tue, 9 Oct 2012 23:23:40 +0000 (16:23 -0700)]
barrier: add test driver, Makefile

My own additions to test barrier.h

9 years agobenchmarks.mk: fixup linker flag
Brian Norris [Tue, 9 Oct 2012 22:01:25 +0000 (15:01 -0700)]
benchmarks.mk: fixup linker flag

9 years agobarrier: fixup atomic initialization
Brian Norris [Tue, 9 Oct 2012 18:57:05 +0000 (11:57 -0700)]
barrier: fixup atomic initialization

9 years agobarrier: add hand-written barrier implementation
Brian Norris [Tue, 9 Oct 2012 18:15:36 +0000 (11:15 -0700)]
barrier: add hand-written barrier implementation

Grabbed from:
http://stackoverflow.com/questions/8115267/writing-a-spinning-thread-barrier-using-c11-atomics

9 years agocommon benchmarks makefile definitions
Brian Norris [Tue, 9 Oct 2012 18:04:10 +0000 (11:04 -0700)]
common benchmarks makefile definitions

9 years agoadd "lock-free queue"
Brian Norris [Tue, 9 Oct 2012 17:57:56 +0000 (10:57 -0700)]
add "lock-free queue"

From:
http://www.codeproject.com/Articles/153898/Yet-another-implementation-of-a-lock-free-circular

License:
http://opensource.org/licenses/bsd-license.php

9 years ago.gitignore
Brian Norris [Tue, 9 Oct 2012 17:57:19 +0000 (10:57 -0700)]
.gitignore