proposal to speed up add_password to existing db

[GoogleCodeExporter]

hi.
in case of huge database, to add more password it is so slow activity because 
the tool has to compare EACH new password with ALL password already inside db 
to be sure that all password is present only one time.

here the question: it is possible to sort the db of already created couple of 
password-hash?
Best sort algoritm asks n*log-of-2(n) 
So, if the db is sorted, the check will be not "n" but only log-of-2(n) (i.e. 
2^20 pass need only 20 check).

So it is possible to add a new option "add_to_sorted_db".

i.e.:

CASE DB IS NOT SORTED (A)
- to add K new passwords to a db with W passwords needs K*W operations.

CASE DB IS SORTED (B)
- to sort W passwords we need W*log(W) plus
- to add K password we need K*log(W)

If K=2^20 and W=2^20 we have

CASE 'A' = 2^40 operation =                    1099511627776
CASE 'B' = (2^20*20)+(2^20*20)= 40*(2^20)=          41943040

of course to sort a db of is slow than compare, but i think a study on this 
matter should be done.

Original issue reported on code.google.com by pyrit.lo...@gmail.com on 2 May 2011 at 11:13

[GoogleCodeExporter]

we can write an opencl kernel to potentially sort a db faster, grabbing N data 
set at once.
some time ago I have read about cl parallel reduction, to compute 'min' of N in 
a parallel way.
your idea should be welcome, more work to do on db side, but more time to 
dedicate to computation then.

Original comment by masterzorag on 2 May 2011 at 4:31