Date: Mon, 16 Jan 2012 18:25:26 +0400 From: Solar Designer <solar@...nwall.com> To: john-dev@...ts.openwall.com Subject: Re: bitmaps On Mon, Jan 16, 2012 at 03:00:35AM +0400, Solar Designer wrote: > hashes c/s VSZ RSS ... > 1M 13M 121 MB 115 MB > 10M 5.7M 1046 MB 1039 MB Curiously, these speeds improve to 33M and 21M, respectively, on 2xE5420 when I build with OpenMP and add the proper #pragma omp directive for the bitmap lookups loop in cracker.c. I only did this as a quick hack, though - the real thing will need to differ in handling of correct guesses (a critical section) - so I am not committing this yet. I think these 2.5x and 3.7x speedups are pretty good considering that even though the system has 8 CPU cores, it only has 4 L2 caches (IIRC, it's 6 MB shared per each two cores, so 4x6 MB total in the system) and probably not much parallelism for RAM accesses (it's more like pipelining). At these numbers of fast hashes, the overall speed is mostly limited by bitmap and hash table lookups. We could even do this sort of parallelization for the lookups for formats where we don't yet have OpenMP parallelization in crypt_all(), but where max_keys_per_crypt is large enough anyway. The format will need to indicate that its get_hash*(), cmp_one(), and cmp_exact() are thread-safe by setting some flag, though. Some further OpenMP speedup may be possible through eliminating the implicit barrier between crypt_all() and the bitmap lookups loop, but this is tricky to implement while preserving the generic program structure (not specific to a hash type). Well, maybe crypt_all() could use nowait and atomic writes to some flags (as well as write barriers), and the lookups loop or rather get_hash*() could spin when it sees a flag that is not yet set (after a read barrier, although this should not matter on x86). We'd be betting that most of the time the flags would be set in time and the spinning would not occur. We might need to use the ordered directive on the parallel loops to make this more likely. These are just some ideas. In general, the wisdom is that OpenMP is not just for individual loops and we could start using it "for real" (beyond per-format crypto code). Alexander
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.