- Boost - lists.boost.org

Idea for O(1) hash-table
by Rani Sharoni 19 Mar '13

19 Mar '13

Hi All, I hope that you will find the following idea interesting. I have been using hash-table with, AFAICT, unique implementation and I thought that it might be handy for boost. The hash table is O(1) *non-amortized* lookup via extremely balanced buckets (for example, max 6 entries per bucket). The implementation itself is absurdly simple ;-) The hash-table is basically variation of linear addressing using double-hashing hash-table with special re-insert strategy. Algorithm for linear addressing (easy to adjust for chained hashing): Consider a two dimensional N*K array – N buckets with up to K elements per bucket. Assume that the zero-key is marking an empty entry. Lookup(key): for (hash = key, I = 0 ; I < K ;++i) { hash = HASH(hash); // double-hashing if (A[hash % N][i] == key) return found; } return not-found; Insert(key): for (hash = key, I = 0 ; I < K ;++i) { hash = HASH(hash); // double-hashing if (A[hash % N][i] == 0) { A[hash % N][i] = key; return true; } } return false; The above insert is basically a bounded double-hashing and as-is it has a low utilization (a bit similar to bloom filter). For example, for 100K buckets and K=6 - insert will fail when the table has less than 50% utilization (i.e. fail to insert though most entries are empty). The trick is to perform “re-insert”: Pick some random element, key1, from failed insert phase, replace it with the new key, and (re) Insert(key1). Retrying up to, say, 12 rounds of re-insert improves the utilization, of N=100K/K=6, to ~97%! Table resize is done (if needed) when such repetitive re-insert fails. Altogether this implementation trade-off insert for fast lookup which is very appealing to caches (i.e. insert done in the expensive path - only after a cache miss). Just for comparison, hash-table using naïve liner probing (A[HASH(key)%N][i]) has only ~80% utilization even when using K=128 (i.e. deep buckets)! Such unbalanced behavior is also typical classical hash-tables with link-lists (chained-hashing) since statistically some buckets will outgrow the average. The performance of the classic double-hashing algorithm itself is quite poor when the table is highly utilize since many steps are required to find empty entries. Though this hash-table is general purposed it has some interesting properties: 1) O(1) non-amortized with very low chance for collisions (each key has its own unique “virtual” bucket). 2) Can be implemented on continuous memory without pointers and with excellent utilization 3) Allow wait free implementation of caches (i.e. no lock or even interlocked needed). 4) Allow caches on shared memory – corruption safe/hazard algorithm (assuming at least 64 bit keys). 5) Allow persistent using direct memory to file mapping (i.e. disk representation is same as in-memory one). 6) Average 50% LRU eviction for caches (i.e. on average entry half from the oldest is evicted) BTW – there is little chance for patenting this algorithm since I already published similar idea in the public domain ;-) Thanks, Rani

4 4

[math] Support for libquadmath/ __float128
by Claas 19 Mar '13

19 Mar '13

I have experimented with the quadmath library included with gcc and the boost::math::constants library and encountered several problems. - typeid is seemingly not supported for __float128, which requires an overload of nameof<__float128> - the stream extraction operator has to be provided for __float128 for string conversion to work - a specialisation of numeric_limits has to be provided. Is there an interest in incorporating __float128 into boost ? If so, would it be a good idea to specialise constants for __float128 as well, apart from float, double and long double? Regards Claas

6 23

Libaries accepted by not in Boost release yet - suitable for GSoC?
by Paul A. Bristow 19 Mar '13

19 Mar '13

I note there are some libraries that have been accepted but are not yet in a Boost release - and development seems to be stalled. This seems unfortunate - much effect from many people has gone into the whole process but we are not quite there yet - so a lot of work may be wasted? No doubt authors have other more pressing priorities J I spotted "Constrained value" and "endian" for example. Are any accepted but unfinished libraries suitable for Google Summer of Code students - with the task being to knock them into final shape? Is anyone willing to mentor these? Paul --- Paul A. Bristow, Prizet Farmhouse, Kendal LA8 8AB UK +44 1539 561830 07714330204 pbristow(a)hetp.u-net.com

5 5

[local_function] End scope function name declaration makes code hard to read.
by Mostafa 18 Mar '13

18 Mar '13

(This is a feature request/inquiry.) I'm just now seriously starting to use local_function, and I'm finding that having to "visually parse" until the end of scope to determine the local function name makes the code much harder to read. Is it possible to declare the function name at the beginning of the scope? (I don't mind having to also register the function name at the end of the scope.) Something like: BLF2(add, (int), (int lhs, int rhs)) { return lhs + rhs; } BLF2_REGISTER(add); Having said, I don't see why needing an "ending macro" for the local function scope is a requirement (albeit my understanding of the library internals is limited to implementation annex of the documentation). Can't the start macro just expand to something like: //----------------------------- //Macro Generated Output Start. //----------------------------- //Local class definition. //Local class instance registration. //Out of class method definition starts here: inline void local_add::body(int& sum, const int& factor, const int& num) //----------------------------- //Macro Generated Output End. //----------------------------- //User generated content starts here: { return lhs + rhs; } Thanks, Mostafa

4 8

[docs] How to install boost documentation?
by Mostafa 18 Mar '13

18 Mar '13

I'm having a real hard time trying to figure out how to install boost documentation. Can't find any instructions on boost.org nor any on google. Am I missing something really obvious?

2 3

[gil] Pixel arithmetic operations.
by Harg Tholan 18 Mar '13

18 Mar '13

Hi, Has it ever been considered to overload arithmetic operators for "pixel"? In many situations it may be useful to add, sub or divide the value of two or more pixels. Thanks.

2 1

[gil] What is the status of the Gil extension numeric?
by Krzysztof Czainski 18 Mar '13

18 Mar '13

Hello, During my first steps wit Boost.Gil I bumped onto an example [1], that uses the numeric extension. For this extension, the the example [1] and a ling from Boost.Gil docs [4] point to [2], where I couldn't find any Gil extensions to download. Most Google links pointed to the same page, but I finally found [3]. So my questions are: a) Is there a plan to add the extension numeric to Boost? b) Is [3] the newest version? And could the Boost.Gil docs be updated to point to the right place? c) I corrected a few bugs in boost/gil/extension/numeric/sampler.hpp -- is this list the right place to discuss modifications to the numeric extension? Regards, Kris [1] http://www.boost.org/doc/libs/1_53_0/libs/gil/example/resize.cpp [2] http://opensource.adobe.com/gil [3] http://code.google.com/p/gil-contributions/ [4] http://www.boost.org/doc/libs/1_53_0/libs/gil/doc/index.html

3 15

[test] Any dependency on Boost.Test requires C++11 ?
by John Maddock 18 Mar '13

18 Mar '13

At present any test in Boost.Math that depends on Boost.Test fails for GCC prior to 4.5 because the build script for Boost.Test has: <toolset>gcc:<cxxflags>-std=gnu++0x Is this really required? It looks wrong headed to me: * We already have testers that test both C++03 and C++11 modes - so we don't need this to test C++11 support. * It's presence makes testing gcc in C++03 mode impossible if the library uses Boost.Test - so there may be C++03 breakages that we don't know about because of this. * As mentioned above, this is a hard error for GCC prior to 4.5, so those compilers can't be tested either. Can this be safely removed? Many thanks, John.

4 4

[boost.thread] Documentation code error
by Philip Bennefall 16 Mar '13

16 Mar '13

Hello, In the chapter about synchronization in the boost.thread documentation, where the hello world example with the bank account is being shown, I see a small problem in the class: int GetBalance() { mtx_.lock(); int b = balance_; mtx_.unlock(); return balance_; } I believe it should be: int GetBalance() { mtx_.lock(); int b = balance_; mtx_.unlock(); return b; } Kind regards, Philip Bennefall

1 0

Help in setupping regression tests on ARM
by Antony Polukhin 16 Mar '13

16 Mar '13

I've successfully run nests on x86, but on ARM I've got the following message: # Running Boost.Build tests Traceback (most recent call last): File "run.py", line 60, in <module> runner(root) File "/home/pi/boost_maintain/run_trunk/tools_regression_src/regression.py", line 205, in __init__ self.main() File "/home/pi/boost_maintain/run_trunk/tools_regression_src/regression.py", line 566, in main getattr(self,action_m)() File "/home/pi/boost_maintain/run_trunk/tools_regression_src/regression.py", line 531, in command_regression self.command_test() File "/home/pi/boost_maintain/run_trunk/tools_regression_src/regression.py", line 329, in command_test self.command_test_boost_build() File "/home/pi/boost_maintain/run_trunk/tools_regression_src/regression.py", line 369, in command_test_boost_build "boost/bin.v2/libs/any/test/any_test.test")); OSError: [Errno 2] No such file or directory: '/home/pi/boost_maintain/run_trunk/results/boost/bin.v2/libs/any/test/any_test.test' I try to run tests on RaspberryPi, it is armhf. Compilller is GCC-4.6.3, 25Gb of free space on SD card. It looks strange, that I see only a few folders in /home/pi/boost_maintain/run_trunk/results/boost/bin.v2/libs/ (there are only 6 folders) -- Best regards, Antony Polukhin

2 7