Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Mon, 9 Mar 2015 16:30:51 +0300
From: Aleksey Cherepanov <>
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.

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.

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.