1

I want to multi-thread a "brute-force" algorithm.

I have a function bool check(const char *s, size_t n) that checks if the string s of size n is the password or not.

This function is called for all string combinations that are possible with my alphabet (about 90 chars in the alphabet).

I was able to do it in one thread, but now I want to multi-thread it. I also want my threads to each have almost the same amount of work I do not want one thread to have to test 1B combinations and the other one only 1k).

I thought of splitting the load in "batches" of combinations. Each batch would have a start index and a stop index so the thread having the batch has to test all the combinations between start and stop.

What I call the index of a combination is its lexicographical index, for example with alphabet [A, B, C]:

index combination
1        A 
2        B
3        C
4        AA
5        AB
6        AC
7        BA
8        BB
...      ...

For example, a thread who would be assigned the batch with start=4and stop=7 would test combinations AA, AB, AC, BA.

How can I easily generate the combinations for a batch in a thread? The priority is for it to be fast, since the whole point of the program is brute forcing.

Is there another fast way to split the work between threads?

xorspark
  • 15,749
  • 2
  • 29
  • 38
Brendan Rius
  • 610
  • 9
  • 18

1 Answers1

1

Lexicographical order would be fine to work with if you already had all of your strings in a list, but it is not easy at all to work with if you want to be generating the strings. So, I would forget it as an idea.

Instead, what you could do is start 90 threads, give each thread a starting letter to work with, and have each thread consider words consisting of the first letter that it was given, plus all combinations of the remaining letters.

Mike Nakis
  • 56,297
  • 11
  • 110
  • 142
  • 1
    I might suggest dividing the starting characters amongst a number of threads equal to however many logical cores you have, in order to avoid any context-switching overhead – Nic Jan 20 '17 at 23:31
  • 1
    @Nic actually, the way I understand how modern pipelined CPUs work, there can be significant benefits in having way more threads than cores. But let's not argue about this here, because it is a different subject, suitable for a different question and answer. – Mike Nakis Jan 21 '17 at 11:29
  • Looks like there is a good answer here: http://stackoverflow.com/a/24716319/4126177 :) – Brendan Rius Jan 21 '17 at 16:43