Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Improve MemoryPool locality #12

Closed
wants to merge 2 commits into from
Closed

Improve MemoryPool locality #12

wants to merge 2 commits into from

Conversation

arthurprs
Copy link

@arthurprs arthurprs commented Jul 29, 2016 •
edited

Improve cache locality by using a stack for indexes and a continuous block of memory.

Although it now requires a multiplication (at least preserving this API) the operations on the underlining vector are faster and have better locality than the previous underlining deque.

@hisundar
Copy link
Contributor

Thanks Arthur. We have added a simple unit test for this at
https://github.com/couchbase/forestdb/blob/master/tests/unit/mempool_test.cc
but what we observe is that with your patch, there is nearly a 2X slowdown compared to the existing implementation with std::queue.
I am not sure if this slowdown is due to the multiplication overhead or from the underlying STL implementation or something else. I am on OS X with AppleClang 7.3.0.7030031
Please feel free to add an unit test if you find that the stack based implementation shows better behavior with locality.

@arthurprs arthurprs force-pushed the master branch 2 times, most recently from 0060a81 to 6922f3f Compare July 29, 2016 23:41
@arthurprs
Copy link
Author

arthurprs commented Jul 29, 2016 •
edited

That's very good, I wanted some tests while writing this. Although, I think they're not really good as 97+% of the cpu time is spend inside rand() and the fill pattern it's not deterministic.

I updated the code a bit (second commit in this PR) trying to make it more repeatable and a bit less artificial. I had to increase the iterations a lot to mask the noise from spawning/joining the threads and the fill amount shouldn't be too long otherwise it's impossible to measure what we really want to measure.

stack

➜  build git:(master) ✗ tests/unit/mempool_test
basic test with 500000 runs of 8 bins x 1048576bytes in 391647 us PASSED
multi-thread test with 8 threads each with 500000 runs of 8 bins x 1048576bytes in 1107800 usec PASSED

queue

➜  build git:(bebf491) ✗ tests/unit/mempool_test
basic test with 500000 runs of 8 bins x 1048576bytes in 437160 us PASSED
multi-thread test with 8 threads each with 500000 runs of 8 bins x 1048576bytes in 1199590 usec PASSED

This is probably the best case scenario for deque as most stdlib implementations will fit 8 items per node just fine and won't cause any malloc/free. Also, it hardly stress locality, as the benchmark quickly puts everything into L3 and L2.

@hisundar
Copy link
Contributor

hisundar commented Aug 1, 2016

Thanks for the patch, Arthur! If this is your first code contribution to Couchbase, you'll need to fill out our Contributor License Agreement (http://review.couchbase.org/#/settings/agreements), which basically just declares that you created the code and are allowing us to release it under the Apache license.

@arthurprs arthurprs force-pushed the master branch 2 times, most recently from 57d9b0b to af55b52 Compare August 1, 2016 20:03
@arthurprs
Copy link
Author

I just filled it and rebased the patch.

@arthurprs
Copy link
Author

Are you still interested in this? If yes I can rebase it and fix the conflicts.

@hisundar
Copy link
Contributor

Yes, we are, sorry for the delay, Arthur. As it turns out I don't have the permission to merge pull requests. But I have notified the ones who do. Thanks again

@arthurprs
Improve MemoryPool locality
8346bf4 
Improve cache locality by using a stack for indexes
and a continuous block of memory.
@arthurprs
Update mempool perf test
261dc05
@arthurprs
Copy link
Author

I've rebased the commits on top of master.

@arthurprs arthurprs closed this Jan 20, 2017
ns-codereview pushed a commit that referenced this pull request Aug 19, 2021
@daverigby @trondn
Fix leaks in compact_functional_test
db3a673 
As reported by ASan:

    ==25822==ERROR: LeakSanitizer: detected memory leaks

    Direct leak of 721424 byte(s) in 11 object(s) allocated from:
	#0 0xffff9f6d18bc in malloc (/opt/gcc-10.2.0/lib64/libasan.so.6+0x9d8bc)
	#1 0x4b0284 in hash_init ../forestdb/src/hash.cc:32
	#2 0x40e254 in _fname_create ../forestdb/src/blockcache.cc:806
	#3 0x410698 in bcache_write ../forestdb/src/blockcache.cc:1063
	#4 0x457dc8 in filemgr_read ../forestdb/src/filemgr.cc:2147
	#5 0x4474d4 in _docio_read_through_buffer(docio_handle*, unsigned long, err_log_callback*, bool) ../forestdb/src/docio.cc:711
	#6 0x4474d4 in _docio_read_length ../forestdb/src/docio.cc:803
	#7 0x44c8c0 in docio_read_doc ../forestdb/src/docio.cc:1242
	#8 0x4d6a3c in fdb_kvs_header_read ../forestdb/src/kv_instance.cc:1142
	#9 0x485b94 in _fdb_open ../forestdb/src/forestdb.cc:2076
	#10 0x4adfbc in _fdb_recover_compaction(_fdb_kvs_handle*, char const*) ../forestdb/src/forestdb.cc:585
	#11 0x4869ac in _fdb_open ../forestdb/src/forestdb.cc:2237
	#12 0x486f74 in fdb_open ../forestdb/src/forestdb.cc:848
	#13 0x525da0 in compact_rename_to_original_test() ../forestdb/tests/functional/compact_functional_test.cc:525
	#14 0x546878 in main ../forestdb/tests/functional/compact_functional_test.cc:3904
	#15 0xffff9e4e2ce0 in __libc_start_main (/lib64/libc.so.6+0x1fce0)
	#16 0x404c4c  (/home/couchbase/server/build/forestdb/tests/functional/compact_functional_test+0x404c4c)

    Direct leak of 721424 byte(s) in 11 object(s) allocated from:
	#0 0xffff9f6d18bc in malloc (/opt/gcc-10.2.0/lib64/libasan.so.6+0x9d8bc)
	#1 0x4b0284 in hash_init ../forestdb/src/hash.cc:32
	#2 0x40e254 in _fname_create ../forestdb/src/blockcache.cc:806
	#3 0x410698 in bcache_write ../forestdb/src/blockcache.cc:1063
	#4 0x457dc8 in filemgr_read ../forestdb/src/filemgr.cc:2147
	#5 0x4474d4 in _docio_read_through_buffer(docio_handle*, unsigned long, err_log_callback*, bool) ../forestdb/src/docio.cc:711
	#6 0x4474d4 in _docio_read_length ../forestdb/src/docio.cc:803
	#7 0x44c8c0 in docio_read_doc ../forestdb/src/docio.cc:1242
	#8 0x4d6a3c in fdb_kvs_header_read ../forestdb/src/kv_instance.cc:1142
	#9 0x485b94 in _fdb_open ../forestdb/src/forestdb.cc:2076
	#10 0x486f74 in fdb_open ../forestdb/src/forestdb.cc:848
	#11 0x524460 in compaction_delete_old_test() ../forestdb/tests/functional/compact_functional_test.cc:345
	#12 0x546874 in main ../forestdb/tests/functional/compact_functional_test.cc:3903
	#13 0xffff9e4e2ce0 in __libc_start_main (/lib64/libc.so.6+0x1fce0)
	#14 0x404c4c  (/home/couchbase/server/build/forestdb/tests/functional/compact_functional_test+0x404c4c)

Change-Id: I6179654af9da764d4ceed04fb2702ca84f43c874
Reviewed-on: http://review.couchbase.org/c/forestdb/+/159308
Tested-by: Build Bot <build@couchbase.com>
Reviewed-by: Trond Norbye <trond.norbye@couchbase.com>
greensky00 added a commit to greensky00/forestdb that referenced this pull request Sep 5, 2023
@greensky00
Make fdb_estimate_space_used work in bottom-up mode (couchbase#12)
cdc01c3
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

None yet
2 participants
@arthurprs @hisundar