Queues

[aakoshh]

Implements TChan, TQueue and TBQueue from the book, plus a TVecDequeue to see the effect of having a single data structure for reads and writes. All of them implement the TQueueLike trait with a read and write method to pop and push from the queue.

The PR has benchmarks for them:

$ cargo bench bench_queue
   Compiling stm-core v0.4.0 (/home/aakoshh/projects/samples/rust/rust-stm/stm-core)
    Finished bench [optimized] target(s) in 2.58s
     Running unittests (target/release/deps/stm_core-7fe29cf21dbbe45b)

running 12 tests
test queues::tbqueue::bench_queue::one_thread_repeat_write_read        ... bench:   1,164,890 ns/iter (+/- 27,107)
test queues::tbqueue::bench_queue::one_thread_write_many_then_read     ... bench:   1,371,410 ns/iter (+/- 5,625)
test queues::tbqueue::bench_queue::two_threads_read_write              ... bench:   2,356,881 ns/iter (+/- 200,454)
test queues::tchan::bench_queue::one_thread_repeat_write_read          ... bench:     984,113 ns/iter (+/- 7,708)
test queues::tchan::bench_queue::one_thread_write_many_then_read       ... bench:   1,116,569 ns/iter (+/- 11,115)
test queues::tchan::bench_queue::two_threads_read_write                ... bench:   1,064,608 ns/iter (+/- 170,726)
test queues::tqueue::bench_queue::one_thread_repeat_write_read         ... bench:     732,992 ns/iter (+/- 6,065)
test queues::tqueue::bench_queue::one_thread_write_many_then_read      ... bench:     986,591 ns/iter (+/- 6,985)
test queues::tqueue::bench_queue::two_threads_read_write               ... bench:     835,677 ns/iter (+/- 105,990)
test queues::tvecdequeue::bench_queue::one_thread_repeat_write_read    ... bench:     824,904 ns/iter (+/- 19,363)
test queues::tvecdequeue::bench_queue::one_thread_write_many_then_read ... bench:   3,058,232 ns/iter (+/- 25,077)
test queues::tvecdequeue::bench_queue::two_threads_read_write          ... bench:   2,019,408 ns/iter (+/- 322,393)

test result: ok. 0 passed; 0 failed; 0 ignored; 12 measured; 40 filtered out; finished in 24.22s

[aakoshh]

Ah, sorry I just saw now in https://github.com/Marthog/rust-stm/issues/15 that you have a different repo for data structures, or at least you didn't want them in stm-core, which makes sense. I was looking at some Scala implementations and they all had some collections; I thought queues are an especially useful integration pattern for things like a thread that persists changes to the database, so it would be good to have them available.