
Date: Mon, 9 Mar 2015 16:30:51 +0300 From: Aleksey Cherepanov <lyosha@...nwall.com> To: johndev@...ts.openwall.com Subject: Re: 256/128 bit integer arithmatic I'll add a bit of impractical (maybe unrelated) theory... On Mon, Mar 09, 2015 at 06:36:36PM +0530, Sayantan Datta wrote: > The task is to build a hashtable which requires exactly 2 memory operations > per lookup. It is very easy to do a lookups that takes exactly 2 memory > accesses, hence no control divergence, hence a good fit for GPUs. Also the > space required for the hashtable is O(n). But building them is quite > intensive. Building a hash table for 10M hashes takes 30 sec while 100M > might take 10 minutes to build. Significant amount of the time is spent on > doing modulo operations, which cannot be done using simple & operators. For a given set of values, you can make a perfect hash table. https://en.wikipedia.org/wiki/Perfect_hash For a small set (up to 256 elements) you may try something like: ((v >> C1) ^ (v >> C2) ^ (v >> C3)) & 0xff where v is a input value and C1, C2, C3 are constants. You compute these constants when you take a set (with this particular function, it may not be possible to construct a function for a certain given set). And the function gives an index. Though for 10M, something more complex is needed. To compute variable part of function for each set may be quite long even with smarter algorithms. Also the variable part should be inserted into the code. It may add compilation time or need "low level gpu" task to be done.  Regards, Aleksey Cherepanov
Powered by blists  more mailing lists