Home / This developer's life / 5/17/2019, Fast File Finder 1.2.4 and optimizing memory usage in Go edit
Try Documentalist, my app that offers fast, offline access to 190+ programmer API docs.

I released version 1.2.4 of Fast File Finder, a program to quickly find files by name on Windows.
There are 2 lessons here.
Lesson 1: if you use the software you write, you'll be more likely to improve it.
It all started with me using latest version and it crashing without a trace. If it happened to the user and reported to me, I would be stuck. There's nothing to go on: the program just seemingly vanished.
My theory was that a goroutine crashed and took the program down with it.
I only have few of those so I've added a way to catch crashes in goroutine so that they get logged and don't bring down the program.
It's useful functionality but it wasn't the problem.
I got a small hint in that 64-bit version was working fine while 32-bit version wasn't.
I then ran the program under WinDBG debugger hoping to catch the crash. WinDBG is not a good debugger for Go programs because it only understands .pdb symbols, while Go only produces DWARF symbols, but Go's native debugger delve only supports 64 bit programs, and 64-bit version didn't crash.
Unfortunately the program didn't crash. It looked like it exited without getting into a crash state.
My next theory was that it was related to running out of memory so I ran it and just observed memory usage in Task Manager.
Bingo: the used space quickly grew to almost 1 GB. It's not necessarily amount of physically used memory but given that 32-bit processes have access to only 2 GB of memory / virtual space, it's not surprising that a managed runtime like Go's has issues after reserving 2 GB.
Fast File Finder works by building an in-memory index. The thing is: the index was only around 200 MB, far from 1 GB.
To understand why 200 MB of data can gobble much more real memory requires understanding Go slices and how they grow.
The index was stored as a single []byte slice. It's a more compact and GC-friendly way of storing a list of directories and files than a naive way of using a string for each directory and file. For example, a string overhead is at a minimum 2 machine words (one for a pointer to string data and one for string length). That's 2 x 8 = 16 bytes per string on 64-bit machine. Add overhead of allocating each string separately and overhead of scanning those strings during GC cycles.
Index building process scans a hard-drive, accumulates up to 1 MB of data and appends this data to the index. So it looks like this:
var index []byte
var indexChunk []byte
for {
	indexChunk = scanNextDriveChunk()
  index = append(index, indexChunk...)
}
Here lies the issue: when we append to index, Go runtime has to expand index slice which means we need to allocate memory for new, bigger slice, copy data from existing slice, append new data, free the old slice. This memory copying is expensive.
Go runtime is smart about it: to avoid this expensive re-allocation on every append, it allocates more than strictly necessary for new slice. As a rule of thumb think of it as doubling the size of the slice.
That's a good system but it does have a trade-off: the bigger the slice, the more memory you're (potentially) wasting.
Imagine the slice is 128 kB in size and you append 1 kB of data. Go will double the size of the slice to 256 kB and you'll be wasting 127 kB of memory at that point.
In my case, expanding by 1 MB to 200 MB would have allocated much more than 200 MB.
The solution was relatively easy: the index became a slice of 1 MB chunks:
var index [][]byte
var indexChunk []byte
for {
	indexChunk = scanNextDriveChunk()
  index = append(index, indexChunk)
}
I had to rewrite the scan and search code but it wasn't hard.
After the change even the 32 bit version could scan my drive.
Unfortunately, this isn't 100% fix. The reason the program worked before and stopped working recently was that I have more files on my hard-drive now.
I'm sure that people have hard-drives with enough files to go over the limit of a 32-bit process.
One way to mitigate this would be to ship 64-bit version. I avoided that because some people might still have 32-bit OS version, but I probably should stop caring because I think it's a very small number.
For really large indexes the solution would be to store the index on disk. The search would be slower but truly limitless.
A hybrid solution would work too: up to certain size, keep the index in memory. Over that size, use disk.

Feedback about page:

Feedback:
Optional: your email if you want me to get back to you:

Share on        

Need fast, offline access to 190+ programmer API docs? Try my app Documentalist for Windows