[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20150309133051.GA8135@openwall.com>
Date: Mon, 9 Mar 2015 16:30:51 +0300
From: Aleksey Cherepanov <lyosha@...nwall.com>
To: john-dev@...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
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
