First let's mention a bug / issue:
- Your
passwords variable is accessed (read and modified) from multiple goroutines without any syncronization: this is a race condition!
Primary problem
Your memory problem arises from launching a tremendous amount of goroutines. For example when you call compute() with n = 6 (to try passwords with a length of 6), it will create:
36^5 = pow(36, 5) = 60466176
(36 is the length of your alphabet; 5 is the prefix value for the condition prefix == n-1 when compute() stops spawning new goroutines)
60 million goroutines!
Goroutines are lightweight, but not that lightweight! Even if managing 1 goroutine would cost only 1 KB memory (it has its own stack etc.), this would require 60 GB memory! Understandable you run out of it. Your code spawns goroutines at a much quicker rate than they complete. (It should be noted that nothing in your code prevents spawning these new goroutines before any would be completed, so this is kind of worst case but still...)
An easy fix!
But the good news is that there is a really easy fix to this tremendous number of goroutines: simply do not spawn many goroutines.
A trivial way to limit spawning goroutines is that when you would spawn them, bind it to a condition to keep them at bay. For example launch 36 goroutines to process passwords starting with the different letters, but after that let 1 goroutine try all the combinations with that starting letter.
We can test this "first letter" condition by comparing prefix to 0:
for i := range alfabeto {
wgFather.Add(1)
if prefix == 0 {
go compute(prefix+1, n, fmt.Sprintf("%s%c", a, alfabeto[i]), wgFather)
} else {
compute(prefix+1, n, fmt.Sprintf("%s%c", a, alfabeto[i]), wgFather)
}
}
By inserting this condition and the else branch just calling compute() on the same goroutine, you keep your goroutine number and memory usage at bay! But still, you utilize multiple goroutines and multiple CPU cores.
There is a minor "downside": you have no control how these 36 goroutines finish compared to each other, there may be a "relaxed" period when only 1 or 2 goroutines are running and others are finished, in this relaxed period CPU utilization will not be 100%. More formally CPU utilization will be < 100% if # of goroutines is less than # of CPU cores.
Optimization tips
Here are some optimization tips:
You do unnecessary round-trips: you build potential passwords as string, then when your searchPassword() function computes its MD5, it has to convert it to []byte. Best would be to build password in a []byte. Go stores strings as UTF-8 encoded sequences (see blog post Strings, bytes, runes and characters in Go for details), and all your alphabet letters map to bytes one-to-one in UTF-8 encoding, so you could just use their byte value for faster building.
In your searchPassword() when you have the MD5 of the potential password, you always iterate over all crackable MD5 strings and you compare to all. This is a waste, you could sort the crackable MD5 values and use binary search to find if the potential is in it (sorting and binary search is implemented in the sort package). Or even better: you could build a map from the crackable MD5 strings, and just check if the candidate is in the map (now this check would be O(1) complexity instead of O(log n) of the binary search).
It is also an unnecessary round-trip to convert a calculated MD5 to string in order to check if it is a crackable one. Best would be to convert the crackable MD5 values to a byte array (note: array and not slice), and when you have the MD5 of a potential password as an array, you can check if it is a crackable one without converting it to string. Arrays are comparable in Go (unlike slices!), so you could also build a map from the MD5 arrays to check if a potential MD5 is in the map.
Also note that your algorithm generates passwords multiple times. For example if you want to check passwords with a length of 3, these 3-letter passwords are essentially all the 2-letter passwords +1. But you don't make use of this, you always generate all passwords with a given length from "scratch".
Utilizing these tips would speed up your algorithm big time; not just because we got rid of lots of needless computation / conversion, but also because much less "garbage" will be generated for the GC.
Alternative
An alternative way of implementing this brute-force cracker would be to use the producer-consumer pattern. You could have a designated producer goroutine that would generate the possible passwords, and send them on a channel. You could have a fixed pool of consumer goroutines (e.g. 5 of them) which would loop over the channel on which generated passwords are delivered, and each would do the same: receive passwords, hash them (MD5) and check if it matches a crackable one.
The producer goroutine could simply close the channel when all combinations were generated, properly signalling consumers that no more passwords will be coming. The for ... range construct on a channel handles the "close" event and terminates properly.
This would result in a clean design, would result in fixed number of goroutines, and it would always utilize 100% CPU. It also has the advantage that it can be "throttled" with the proper selection of the channel capacity (buffered channel) and the number of consumer goroutines.
Here is how this producer-consumer could look like in Go if someone wants to play with it (also note that I elaborated this with full examples and much deeper explanation in StackOverflow question Is this an idiomatic worker thread pool in Go?):
var wg sync.WaitGroup
func produce(ch chan<- []byte) {
// Now generate all passwords:
for {
if noMore { // If no more passwords
close(ch)
break
}
pass := ... // Here generate next password
ch <- pass // send it for processing
}
}
func consume(ch <-chan []byte) {
defer wg.Done()
for pass := range ch {
// Hash, check
}
}
func main() {
ch := make(chan []byte, 100) // Buffered channel
// Start consumers:
for i := 0; i < 5; i++ { // 5 consumers
wg.Add(1)
go consume(ch)
}
// Start producing: we can run this in the main goroutine
produce(ch)
wg.Wait() // Wait all consumers to finish processing passwords
}
This blog post is an excellent introduction to parallel computation in Go using goroutines and channels:
Go Concurrency Patterns: Pipelines and cancellation
Further optimization tip
Now if you go with this producer-consumer goroutine model, another optimization becomes available.
The md5.Sum() function (which takes a []byte and returns the MD5 checksum of its content) always creates a new, internal md5.digest value which is used to do the MD5 hashing. Then it is discarded.
Now if we have a small, fixed pool of consumer goroutines, we can now create and it is profitable to create a designated MD5 hasher for each with the md5.New() function. To what end? We can use the returned hasher (which is of type hash.Hash) to compute MD5 hashes, but what's cool is that we can reuse it to compute hashes of multiple byte slices.
hash.Hash implements io.Writer so we can write any []byte into it of which we want to compute the MD5 hash, and it also has a Hash.Sum() method which returns the MD5 hash, giving the option to not create a new array return value which will hold the calculated MD5, but we can pass our slice to it in which we want the result. We can also create prepared arrays ([16]byte) and slice them to obtain a slice []byte, and do this for all of the consumer goroutines. As a result, we can further suppress "memory-garbage" generation and reduce GC work. Once we queried the MD5 sum of a password, we can simply call Hash.Reset() to re-initialize the hasher for the next password.
