multi_index instead of unordered_map

[ghost]

before [denis@f22 helix]$ ./order_book_perf_test order_book::add() 61 ns/op order_book::cancel() 10 ns/op order_book::remove() 32 ns/op

after [denis@f22 helix]$ ./order_book_perf_test order_book::add() 48 ns/op order_book::cancel() 10 ns/op order_book::remove() 19 ns/op

[penberg]

@divaykin Can you please add

sudo apt-get install libboost-all-dev

in the before_install section of .travis.yml to fix Travis CI build?

[ghost]

seems like boost version < 1.55 installed. i.e. no emplace method. what's the best way to get a new version? should we get it from source?

[penberg]

@divaykin Yeah, it's probably easiest to try to install from sources like we do with libuv.

[ghost]

@penberg does it worth the hassle? do you see the same improvement i see / like the code?

[penberg]

What CPU do you have? Which GCC version and Boost version are you testing with? I'm using a Haswell and running Fedora 21 which has:

• gcc version 4.9.2 20150212 (Red Hat 4.9.2-6) (GCC)
• boost-devel 1.55.0

Order book performance is worse with your changes:

Before:

[penberg@nero helix]$ taskset -c 1 ./tests/order_book_perf_test 
order_book::add()    54 ns/op
order_book::cancel() 9 ns/op
order_book::remove() 28 ns/op

After:

[penberg@nero helix]$ taskset -c 1 ./tests/order_book_perf_test 
order_book::add()    68 ns/op
order_book::cancel() 18 ns/op
order_book::remove() 22 ns/op

[ghost]

gcc version 5.1.1 20150618 (Red Hat 5.1.1-4) (GCC) boost 1.57.0

fc22. CPU is an old one, tomorrow will try on Broadwell also.

[ghost]

could you please try the newer software if possible? thx @penberg

[penberg]

@divaykin I can try newer versions but if performance is better on Broadwell I think we can just merge this.

[ghost]

i'd very much appreciate independant benchmark, maybe there is something wrong i'm doing

[ghost]

i think boost 1.56 had really a lot of changes to Multi Index see http://www.boost.org/doc/libs/1_59_0/libs/multi_index/doc/release_notes.html probably just getting newer boost should be sufficient

[ghost]

Intel(R) Core(TM) i7-5600U CPU @ 2.60GHz
before:
[denis@x1 build]$ taskset -c 2 ./tests/order_book_perf_test 
order_book::add()    64 ns/op
order_book::cancel() 12 ns/op
order_book::remove() 34 ns/op

after:
[denis@x1 build]$ taskset -c 2 ./tests/order_book_perf_test 
order_book::add()    49 ns/op
order_book::cancel() 11 ns/op
order_book::remove() 20 ns/op

would be great if you could test with latest boost @penberg thx!

[penberg]

Yes, it indeed is a Boost and GCC issue. I ran the test in a Docker container on my Haswell machine:

[root@af71f34107bf helix]# cat /etc/fedora-release
Fedora release 22 (Twenty Two)
[root@af71f34107bf helix]# gcc -v
gcc version 5.1.1 20150618 (Red Hat 5.1.1-4) (GCC) 

The performance improvement looks similar to yours:

Before:

[root@af71f34107bf helix]# tests/order_book_perf_test
order_book::add()    53 ns/op
order_book::cancel() 10 ns/op
order_book::remove() 28 ns/op

After:

[root@af71f34107bf helix]# tests/order_book_perf_test
order_book::add()    37 ns/op
order_book::cancel() 9 ns/op
order_book::remove() 15 ns/op

I wonder what to do with Travis CI, though. Building Boost from sources was pretty painful when I tried to do it.

[penberg]

I found these instructions:

https://coderwall.com/p/0atfug/installing-boost-1-55-from-source-on-ubuntu-12-04

Perhaps it's not too painful after all...

[ghost]

cool thing this multi index eh? ) sure, i'll try this out.

i was also looking for a fast map replacement but has not found something decent yet.

[ghost]

the build is not taking long but should work