optimise memory footprint of the topic matching #17
Comments
|
Space required can be optimised even further by using bitmap of available next nodes instead of min/count style of branching. |
Closed
abaelhe
added a commit
to abaelhe/libzmq
that referenced
this issue
Jul 17, 2022
Build all projects ** BUILD SUCCEEDED ** bash-3.2# cd bin/Debug/ bash-3.2# for x in ./* ; do ./$x 1> /dev/null 2>/dev/null || echo $x ; done ./test_bind_curve_fuzzer ./test_bind_fuzzer ./test_bind_null_fuzzer ./test_connect_curve_fuzzer ./test_connect_fuzzer ./test_connect_null_fuzzer Segmentation fault: 11 ./test_security_curve ./test_z85_decode_fuzzer bash-3.2# ./test_bind_curve_fuzzer bash-3.2# ./test_bind_curve_fuzzer bash-3.2# ./test_bind_fuzzer bash-3.2# ./test_bind_null_fuzzer bash-3.2# ./test_connect_curve_fuzzer bash-3.2# ./test_connect_fuzzer bash-3.2# ./test_security_curve Segmentation fault: 11 bash-3.2# lldb ./test_security_curve (lldb) target create "./test_security_curve" Current executable set to '/Users/abaelhe/Downloads/libzmq-master/build/bin/Debug/test_security_curve' (x86_64). (lldb) r Process 39009 launched: '/Users/abaelhe/Downloads/libzmq-master/build/bin/Debug/test_security_curve' (x86_64) Process 39009 stopped * thread zeromq#3, name = 'ZMQbg/IO/0', stop reason = signal SIGSEGV frame #0: 0x00007ff80f64f192 libsystem_kernel.dylib`__pthread_sigmask + 10 libsystem_kernel.dylib`__pthread_sigmask: -> 0x7ff80f64f192 <+10>: jae 0x7ff80f64f19c ; <+20> 0x7ff80f64f194 <+12>: movq %rax, %rdi 0x7ff80f64f197 <+15>: jmp 0x7ff80f64a1c5 ; cerror_nocancel 0x7ff80f64f19c <+20>: retq Target 0: (test_security_curve) stopped. (lldb) bt warning: could not find Objective-C class data in the process. This may reduce the quality of type information available. * thread zeromq#3, name = 'ZMQbg/IO/0', stop reason = signal SIGSEGV * frame #0: 0x00007ff80f64f192 libsystem_kernel.dylib`__pthread_sigmask + 10 frame zeromq#1: 0x00007ff80f685acb libsystem_pthread.dylib`pthread_sigmask + 9 frame zeromq#2: 0x00007ff80f5d1d19 libsystem_c.dylib`abort + 112 frame zeromq#3: 0x0000000100333551 libsodium.23.dylib`_out_of_bounds.cold.1 + 17 frame zeromq#4: 0x0000000100316229 libsodium.23.dylib`_out_of_bounds + 9 frame zeromq#5: 0x0000000100316218 libsodium.23.dylib`sodium_free + 408 frame zeromq#6: 0x00000001005a6d0d libzmq.5.dylib`zmq::secure_allocator_t<unsigned char>::deallocate(this=0x00007000014c6ce0, p="", (null)=96) at secure_allocator.hpp:63:56 frame zeromq#7: 0x00000001005a6c25 libzmq.5.dylib`std::__1::allocator_traits<zmq::secure_allocator_t<unsigned char> >::deallocate(__a=0x00007000014c6ce0, __p="", __n=96) at allocator_traits.h:282:13 frame zeromq#8: 0x00000001005a6484 libzmq.5.dylib`std::__1::__vector_base<unsigned char, zmq::secure_allocator_t<unsigned char> >::~__vector_base(this=0x00007000014c6cd0) at vector:488:9 frame zeromq#9: 0x00000001005acae2 libzmq.5.dylib`std::__1::vector<unsigned char, zmq::secure_allocator_t<unsigned char> >::~vector(this=0x00007000014c6cd0 size=0) at vector:579:5 frame zeromq#10: 0x00000001005ac165 libzmq.5.dylib`std::__1::vector<unsigned char, zmq::secure_allocator_t<unsigned char> >::~vector(this=0x00007000014c6cd0 size=0) at vector:574:5 frame zeromq#11: 0x00000001005ab2e7 libzmq.5.dylib`zmq::curve_server_t::process_hello(this=0x000000010182c600, msg_=0x00006000037001e8) at curve_server.cpp:208:1 frame zeromq#12: 0x00000001005aad30 libzmq.5.dylib`zmq::curve_server_t::process_handshake_command(this=0x000000010182c600, msg_=0x00006000037001e8) at curve_server.cpp:104:18 frame zeromq#13: 0x000000010062ccd7 libzmq.5.dylib`zmq::stream_engine_base_t::process_handshake_command(this=0x000000010182d400, msg_=0x00006000037001e8) at stream_engine_base.cpp:491:32 frame zeromq#14: 0x000000010062ba21 libzmq.5.dylib`zmq::stream_engine_base_t::in_event_internal(this=0x000000010182d400) at stream_engine_base.cpp:309:14 frame zeromq#15: 0x000000010062b665 libzmq.5.dylib`zmq::stream_engine_base_t::in_event(this=0x000000010182d400) at stream_engine_base.cpp:243:22 frame zeromq#16: 0x00000001005c0889 libzmq.5.dylib`zmq::kqueue_t::loop(this=0x00006000037000c0) at kqueue.cpp:218:30 frame zeromq#17: 0x00000001005eefa9 libzmq.5.dylib`zmq::worker_poller_base_t::worker_routine(arg_=0x00006000037000c0) at poller_base.cpp:146:51 frame zeromq#18: 0x0000000100637e66 libzmq.5.dylib`thread_routine(arg_=0x0000600003700100) at thread.cpp:256:5 frame zeromq#19: 0x00007ff80f6864e1 libsystem_pthread.dylib`_pthread_start + 125 frame zeromq#20: 0x00007ff80f681f6b libsystem_pthread.dylib`thread_start + 15 (lldb)
bluca
pushed a commit
to abaelhe/libzmq
that referenced
this issue
Aug 10, 2022
…ntation Build all projects ** BUILD SUCCEEDED ** bash-3.2# cd bin/Debug/ bash-3.2# for x in ./* ; do ./$x 1> /dev/null 2>/dev/null || echo $x ; done ./test_bind_curve_fuzzer ./test_bind_fuzzer ./test_bind_null_fuzzer ./test_connect_curve_fuzzer ./test_connect_fuzzer ./test_connect_null_fuzzer Segmentation fault: 11 ./test_security_curve ./test_z85_decode_fuzzer bash-3.2# ./test_bind_curve_fuzzer bash-3.2# ./test_bind_curve_fuzzer bash-3.2# ./test_bind_fuzzer bash-3.2# ./test_bind_null_fuzzer bash-3.2# ./test_connect_curve_fuzzer bash-3.2# ./test_connect_fuzzer bash-3.2# ./test_security_curve Segmentation fault: 11 bash-3.2# lldb ./test_security_curve (lldb) target create "./test_security_curve" Current executable set to '/Users/abaelhe/Downloads/libzmq-master/build/bin/Debug/test_security_curve' (x86_64). (lldb) r Process 39009 launched: '/Users/abaelhe/Downloads/libzmq-master/build/bin/Debug/test_security_curve' (x86_64) Process 39009 stopped * thread zeromq#3, name = 'ZMQbg/IO/0', stop reason = signal SIGSEGV frame #0: 0x00007ff80f64f192 libsystem_kernel.dylib`__pthread_sigmask + 10 libsystem_kernel.dylib`__pthread_sigmask: -> 0x7ff80f64f192 <+10>: jae 0x7ff80f64f19c ; <+20> 0x7ff80f64f194 <+12>: movq %rax, %rdi 0x7ff80f64f197 <+15>: jmp 0x7ff80f64a1c5 ; cerror_nocancel 0x7ff80f64f19c <+20>: retq Target 0: (test_security_curve) stopped. (lldb) bt warning: could not find Objective-C class data in the process. This may reduce the quality of type information available. * thread zeromq#3, name = 'ZMQbg/IO/0', stop reason = signal SIGSEGV * frame #0: 0x00007ff80f64f192 libsystem_kernel.dylib`__pthread_sigmask + 10 frame zeromq#1: 0x00007ff80f685acb libsystem_pthread.dylib`pthread_sigmask + 9 frame zeromq#2: 0x00007ff80f5d1d19 libsystem_c.dylib`abort + 112 frame zeromq#3: 0x0000000100333551 libsodium.23.dylib`_out_of_bounds.cold.1 + 17 frame zeromq#4: 0x0000000100316229 libsodium.23.dylib`_out_of_bounds + 9 frame zeromq#5: 0x0000000100316218 libsodium.23.dylib`sodium_free + 408 frame zeromq#6: 0x00000001005a6d0d libzmq.5.dylib`zmq::secure_allocator_t<unsigned char>::deallocate(this=0x00007000014c6ce0, p="", (null)=96) at secure_allocator.hpp:63:56 frame zeromq#7: 0x00000001005a6c25 libzmq.5.dylib`std::__1::allocator_traits<zmq::secure_allocator_t<unsigned char> >::deallocate(__a=0x00007000014c6ce0, __p="", __n=96) at allocator_traits.h:282:13 frame zeromq#8: 0x00000001005a6484 libzmq.5.dylib`std::__1::__vector_base<unsigned char, zmq::secure_allocator_t<unsigned char> >::~__vector_base(this=0x00007000014c6cd0) at vector:488:9 frame zeromq#9: 0x00000001005acae2 libzmq.5.dylib`std::__1::vector<unsigned char, zmq::secure_allocator_t<unsigned char> >::~vector(this=0x00007000014c6cd0 size=0) at vector:579:5 frame zeromq#10: 0x00000001005ac165 libzmq.5.dylib`std::__1::vector<unsigned char, zmq::secure_allocator_t<unsigned char> >::~vector(this=0x00007000014c6cd0 size=0) at vector:574:5 frame zeromq#11: 0x00000001005ab2e7 libzmq.5.dylib`zmq::curve_server_t::process_hello(this=0x000000010182c600, msg_=0x00006000037001e8) at curve_server.cpp:208:1 frame zeromq#12: 0x00000001005aad30 libzmq.5.dylib`zmq::curve_server_t::process_handshake_command(this=0x000000010182c600, msg_=0x00006000037001e8) at curve_server.cpp:104:18 frame zeromq#13: 0x000000010062ccd7 libzmq.5.dylib`zmq::stream_engine_base_t::process_handshake_command(this=0x000000010182d400, msg_=0x00006000037001e8) at stream_engine_base.cpp:491:32 frame zeromq#14: 0x000000010062ba21 libzmq.5.dylib`zmq::stream_engine_base_t::in_event_internal(this=0x000000010182d400) at stream_engine_base.cpp:309:14 frame zeromq#15: 0x000000010062b665 libzmq.5.dylib`zmq::stream_engine_base_t::in_event(this=0x000000010182d400) at stream_engine_base.cpp:243:22 frame zeromq#16: 0x00000001005c0889 libzmq.5.dylib`zmq::kqueue_t::loop(this=0x00006000037000c0) at kqueue.cpp:218:30 frame zeromq#17: 0x00000001005eefa9 libzmq.5.dylib`zmq::worker_poller_base_t::worker_routine(arg_=0x00006000037000c0) at poller_base.cpp:146:51 frame zeromq#18: 0x0000000100637e66 libzmq.5.dylib`thread_routine(arg_=0x0000600003700100) at thread.cpp:256:5 frame zeromq#19: 0x00007ff80f6864e1 libsystem_pthread.dylib`_pthread_start + 125 frame zeromq#20: 0x00007ff80f681f6b libsystem_pthread.dylib`thread_start + 15 (lldb)
bluca
pushed a commit
that referenced
this issue
Aug 10, 2022
…ntation Build all projects ** BUILD SUCCEEDED ** bash-3.2# cd bin/Debug/ bash-3.2# for x in ./* ; do ./$x 1> /dev/null 2>/dev/null || echo $x ; done ./test_bind_curve_fuzzer ./test_bind_fuzzer ./test_bind_null_fuzzer ./test_connect_curve_fuzzer ./test_connect_fuzzer ./test_connect_null_fuzzer Segmentation fault: 11 ./test_security_curve ./test_z85_decode_fuzzer bash-3.2# ./test_bind_curve_fuzzer bash-3.2# ./test_bind_curve_fuzzer bash-3.2# ./test_bind_fuzzer bash-3.2# ./test_bind_null_fuzzer bash-3.2# ./test_connect_curve_fuzzer bash-3.2# ./test_connect_fuzzer bash-3.2# ./test_security_curve Segmentation fault: 11 bash-3.2# lldb ./test_security_curve (lldb) target create "./test_security_curve" Current executable set to '/Users/abaelhe/Downloads/libzmq-master/build/bin/Debug/test_security_curve' (x86_64). (lldb) r Process 39009 launched: '/Users/abaelhe/Downloads/libzmq-master/build/bin/Debug/test_security_curve' (x86_64) Process 39009 stopped * thread #3, name = 'ZMQbg/IO/0', stop reason = signal SIGSEGV frame #0: 0x00007ff80f64f192 libsystem_kernel.dylib`__pthread_sigmask + 10 libsystem_kernel.dylib`__pthread_sigmask: -> 0x7ff80f64f192 <+10>: jae 0x7ff80f64f19c ; <+20> 0x7ff80f64f194 <+12>: movq %rax, %rdi 0x7ff80f64f197 <+15>: jmp 0x7ff80f64a1c5 ; cerror_nocancel 0x7ff80f64f19c <+20>: retq Target 0: (test_security_curve) stopped. (lldb) bt warning: could not find Objective-C class data in the process. This may reduce the quality of type information available. * thread #3, name = 'ZMQbg/IO/0', stop reason = signal SIGSEGV * frame #0: 0x00007ff80f64f192 libsystem_kernel.dylib`__pthread_sigmask + 10 frame #1: 0x00007ff80f685acb libsystem_pthread.dylib`pthread_sigmask + 9 frame #2: 0x00007ff80f5d1d19 libsystem_c.dylib`abort + 112 frame #3: 0x0000000100333551 libsodium.23.dylib`_out_of_bounds.cold.1 + 17 frame #4: 0x0000000100316229 libsodium.23.dylib`_out_of_bounds + 9 frame #5: 0x0000000100316218 libsodium.23.dylib`sodium_free + 408 frame #6: 0x00000001005a6d0d libzmq.5.dylib`zmq::secure_allocator_t<unsigned char>::deallocate(this=0x00007000014c6ce0, p="", (null)=96) at secure_allocator.hpp:63:56 frame #7: 0x00000001005a6c25 libzmq.5.dylib`std::__1::allocator_traits<zmq::secure_allocator_t<unsigned char> >::deallocate(__a=0x00007000014c6ce0, __p="", __n=96) at allocator_traits.h:282:13 frame #8: 0x00000001005a6484 libzmq.5.dylib`std::__1::__vector_base<unsigned char, zmq::secure_allocator_t<unsigned char> >::~__vector_base(this=0x00007000014c6cd0) at vector:488:9 frame #9: 0x00000001005acae2 libzmq.5.dylib`std::__1::vector<unsigned char, zmq::secure_allocator_t<unsigned char> >::~vector(this=0x00007000014c6cd0 size=0) at vector:579:5 frame #10: 0x00000001005ac165 libzmq.5.dylib`std::__1::vector<unsigned char, zmq::secure_allocator_t<unsigned char> >::~vector(this=0x00007000014c6cd0 size=0) at vector:574:5 frame #11: 0x00000001005ab2e7 libzmq.5.dylib`zmq::curve_server_t::process_hello(this=0x000000010182c600, msg_=0x00006000037001e8) at curve_server.cpp:208:1 frame #12: 0x00000001005aad30 libzmq.5.dylib`zmq::curve_server_t::process_handshake_command(this=0x000000010182c600, msg_=0x00006000037001e8) at curve_server.cpp:104:18 frame #13: 0x000000010062ccd7 libzmq.5.dylib`zmq::stream_engine_base_t::process_handshake_command(this=0x000000010182d400, msg_=0x00006000037001e8) at stream_engine_base.cpp:491:32 frame #14: 0x000000010062ba21 libzmq.5.dylib`zmq::stream_engine_base_t::in_event_internal(this=0x000000010182d400) at stream_engine_base.cpp:309:14 frame #15: 0x000000010062b665 libzmq.5.dylib`zmq::stream_engine_base_t::in_event(this=0x000000010182d400) at stream_engine_base.cpp:243:22 frame #16: 0x00000001005c0889 libzmq.5.dylib`zmq::kqueue_t::loop(this=0x00006000037000c0) at kqueue.cpp:218:30 frame #17: 0x00000001005eefa9 libzmq.5.dylib`zmq::worker_poller_base_t::worker_routine(arg_=0x00006000037000c0) at poller_base.cpp:146:51 frame #18: 0x0000000100637e66 libzmq.5.dylib`thread_routine(arg_=0x0000600003700100) at thread.cpp:256:5 frame #19: 0x00007ff80f6864e1 libsystem_pthread.dylib`_pthread_start + 125 frame #20: 0x00007ff80f681f6b libsystem_pthread.dylib`thread_start + 15 (lldb)
benjdero
pushed a commit
to benjdero/libzmq
that referenced
this issue
Feb 20, 2023
Removed HELLO_OK command
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
There's still one possibility for optimisation though: If, at any particular place of the tree there's a single-branch node (currently the memory footprint optimisation you've noticed), the associated structure could possibly hold up to say 8 subsequent characters. The idea is that single-branch nodes tend to appear in strings. Consider following example. Plus signs correspond to real branchings while minus signs denote strings of single-branch nodes:
The whole point is to significantly lower memory footprint which in turn should have severe impact on performance. Specifically with large search trees it may happen that some parts of the tree are eliminted from the CPU cache. In such case, access to physical memory can slow down the algorithm by an order of magnitude. Thus keeping the data structure as compact as possible will make it much faster, even for sparsely used topics.
The text was updated successfully, but these errors were encountered: