Originally published on my blog
Do you know the fable of the frog and the boiling water? It goes like this:
If you drop a frog in a pot of boiling water, it will of course frantically try to clamber out. But if you place it gently in a pot of tepid water and turn the heat on low, it will float there quite placidly. As the water gradually heats up, the frog will sink into a tranquil stupor, exactly like one of us in a hot bath, and before long, with a smile on its face, it will unresistingly allow itself to be boiled to death.
At least that’s how Daniel Quinn’s tells it in The Story of B.
It is a powerful metaphor, although if you read the Wikipedia article, it turns out frogs do not actually behave that way.
But I think there’s still some truth it in: if you experience some increasing pain gradually enough, you may not realizing how much you are actually suffering until it’s too late. At least it’s what happened to me.
Let’s start at the beginning, before we start talking about Rust, refactoring, performance bugs and the weaknesses of the human mind.
Part 1: The setup
A long time ago, I realized I spent far too much time typing cd
to navigate between project directories, and that the default ctrl-r
binding for zsh
was a bit awkward to use for me.
Then I realized I could solve both of those problems by writing two very similar commands: cwd-history
and cmd-history
.
Let’s talk about the former. It’s a command-line tool that takes two actions, add
and list
. Here’s how it works:
-
cmd-history add
takes one parameter and adds it to a “database” in~/.local/share/dm-tools/commands-history
. The database is just a file with one command per line. -
cmd-history list
simply dumps the contents of the database tostdout
. - Then, there’s a
zsh
hook to run right after a command has been read and is about to be executed. In the hook,cmd-history add
is called with the text of the last command. - Finally,
zsh
is configured so that whenctrl-r
is pressed, the output ofcmd-history list
is piped throughfzf
and then the selected command is run.
I use a similar program called cwd-history
that does exactly the same thing but for the working directories. It runs in another zsh hook called chpwd
, and is triggered by typing the command z
1
There are a few specificities like making sure the entries are not duplicated or ensuring that every symlink in the added path is resolved, but we’ll get to that later.
Part 2: RIR
The two programs were written in Python and shared a ton of functionality but since I am a lazy programmer I did not bother with refactoring the code.
But something was bugging me. There was a small noticeable delay whenever I was using them, particularly on old hardware. So I decided to try and rewrite them in Rust. And surely when I measured the performance, there was a huge difference in the startup time: Rust compiles directly to machine code, and there was no need to wait for the Python interpreter to start. I was happy.
Part 3: the switch to Kakoune
A few months ago, I switched from Neovim to Kakoune for my main text editor and was faced with a problem.
Kakoune does not have any persisting state by design, and I was missing a particular vim feature that allowed me to quickly select any recently opened file (aka. MRU files).
But I already knew how to solve that! I wrote yet another tool called mru-files
for reading and writing the MRU files in another database, and write a bit of Kakoune script:
# Call `mru-files add` with the buffer name when opening a new buffer
hook global BufOpenFile .* %{ nop %sh{ mru-files add "${kak_hook_param}" } }
# Call `mru files list` when pressing <leader key>o:
map global user o
-docstring 'open old files'
':evaluate-commands %sh{ mru-files list --kakoune }<ret>'
Note the --kakoune
option when calling mru-files list
: we need to call the menu
command so that we can present the list of MRU files to the user and open the file when it's selected.
It looks like this:
menu
"/foo.txt" "edit -existing 'foo.txt:'"
"/bar.txt" "edit -existing 'bar.txt'"
...
While I was it, I also added a --kakoune
argument to cwd-history list
so that I could switch to previously visited directories directly from Kakoune:
map global cd o
-docstring 'open old working directory'
':evaluate-commands %sh{ cwd-history list --kakoune }<ret>'
Part 4: the refactoring
So now I was faced with three very similar code written in Rust. It was time for a refactoring 2
Here’s what I did:
- First, I added a trait called
EntryCollection
that contained methods namedadd
andlist
pub trait EntriesCollection {
fn add(&mut self, entry: &str);
fn list(&self) -> &Vec<String>;
}
- The trait was implemented by three structs:
Commands
,WorkingDirs
andMruFiles
.
pub struct Commands {
entries: Vec<String>,
}
impl EntriesCollection for Commands {
// ...
fn add(&mut self, entry: &str) {
// Deduplicate the entry and store it in self.entries
// ...
}
fn list(&self) -> Vec<String> {
// return self.entries
}
}
pub struct WorkingDirs{
entries: Vec<String>,
}
impl EntriesCollection for WorkingDirs {
// ...
fn add(&mut self, entry: &str) {
// Convert the entry to a path, check if it exists,
// then canonicalize it and insert it in self.entries
}
}
(and similar code for MruFiles)
- I wrote a
Storage
struct to interact with the database:
impl Storage {
pub fn new(
mut entries_collection: Box<EntriesCollection>,
path: &std::path::PathBuf,
) -> Storage {
let db_path = path.join(entries_collection.name());
let entries = read_db(&db_path);
for entry in entries {
entries_collection.add(&entry);
}
Storage {
db_path,
entries_collection,
}
}
pub fn list(&self) -> &Vec<String> {
&self.entries_collection.list()
}
pub fn add(&mut self, entry: &str) {
&mut self.entries_collection.add(&entry);
write_db(&self.db_path, &self.list())
}
- I wrote
StorageManager
struct to instantiate theStorage
struct with the correctEntriesCollection
implementation depending on aStorageType
enum:
pub enum StorageType {
CwdHistory,
CommandsHistory,
FilesHistory,
}
pub struct StorageManager {
// ...
}
impl StorageManager {
pub fn new(storage_type: StorageType) -> Self {
let entries: Box<EntriesCollection> = match storage_type {
StorageType::CwdHistory => Box::new(WorkingDirs::new()),
StorageType::CommandsHistory => Box::new(Commands::new()),
StorageType::FilesHistory => Box::new(MruFiles::new()),
};
};
let storage = Storage::new(entries, &app_dir);
StorageManager { storage }
}
pub fn list(&self) {
// Delegates to self.storage.list()
}
pub fn add(&mut self, entry: &str) {
// Delegates to self.storage.add()
}
}
- And finally, I wrote three
main
functions that called theStorageManager
constructor, passing it the enum variant.
// In src/bin/cmd-history.rs
use dm_tools::StorageType;
fn main() {
// ...
dm_tools::run_storage_manager(StorageType::CommandsHistory)
}
// In src/bin/cwd-history.rs
use dm_tools::StorageType;
fn main() {
// ...
dm_tools::run_storage_manager(StorageType::CwdHistory)
}
// In src/bin/mru-files.rs.rs
use dm_tools::StorageType;
fn main() {
// ...
dm_tools::run_storage_manager(StorageType::FilesHistory)
}
And that was my first mistake: I forgot to measure performance after the refactoring. I was sure the code was correct. After all, if it compiles, it works, right?
And sure enough, the code did work. I could open MRU files and old project directories from Kakoune, and I was quite pleased with myself.
Of course, by now you should have guessed there’s a horrible performance bug in the code above. Did you spot it? If you did, congrats! I certainly did not at the time.
Part 5: The peer programming session
The refactoring took place 6 months ago. I am using those tools at work, which means I was using those commands for 6 months, 5 days a week. The database files contained thousands of entries. The horrible bug was still there, consuming CPU cycles without a care in the world, and I did not notice anything.
Fortunately, I did a peer programming session with one of my colleagues and something weird happened. It got bored watching my zsh prompt getting stuck when I was using the z
and ctrl-r
shortcuts.
I then measured the performance of my tools again and I found that the cmd-history list
command took 1.7 seconds to run. That’s one thousand and seven hundred milliseconds. It’s a very long time. No wonder my colleague got bored! What’s amazing though is that I did not notice anything wrong until he told me about it.
Part 6: The fix
Now it’s time to squash the bug. The culprit lies here, in the Storage
constructor:
impl Storage {
pub fn new(
mut entries_collection: Box<EntriesCollection>,
path: &std::path::PathBuf,
) -> Storage {
let db_path = path.join(entries_collection.name());
let entries = read_db(&db_path);
for entry in entries {
entries_collection.add(&entry);
}
Storage {
db_path,
entries_collection,
}
}
}
We’re reading each line of the database file, and passing it to EntriesCollection.add()
. This means we keep calling the add()
method over and over. It does not do much, but it still has to go through all the entries when performing deduplication. This is a classic case of the Shlemiel algorithm and it explains the abysmal performance of the tool as soon as the database gets big enough.
I believe I wrote the code that way because I thought it would be nice to somehow “validate” the entries when reading the database. That way, if the algorithm in the add
method changed, the database will be migrated automatically. Another classical mistake named YAGNI: it’s doubtful I’ll ever need to migrate the database, and when I need to, I’ll probably just have to write a tiny throw-away script to do it.
Anyway, now that we’ve decided the “auto migrating” feature can go away, we can solve our performance issue by adding an add_all
method to the trait, and replacing the for
loop in the Storage
constructor:
pub trait EntriesCollection {
fn add(&mut self, entry: &str);
+ fn add_all(&mut self, entres: Vec<String>);
fn list(&self) -> &Vec<String>;
}
impl Storage {
pub fn new(
mut entries_collection: Box<EntriesCollection>,
path: &std::path::PathBuf,
) -> Storage {
let db_path = path.join(entries_collection.name());
let entries = read_db(&db_path);
- for entry in entries {
- entries_collection.add(&entry);
- }
+ entries_collection.add_all(entres);
Storage {
db_path,
entries_collection,
}
}
}
In turn, this means we need to implement the add_all()
method on all structs:
impl EntriesCollection for Commands {
// ...
fn add_all(&mut self, entries: Vec<String>) {
self.entries = entries;
}
}
impl EntriesCollection for WorkingDirs {
// ...
fn add_all(&mut self, entries: Vec<String>) {
self.entries = entries;
}
}
impl EntriesCollection for MruFiles {
// ...
fn add_all(&mut self, entries: Vec<String>) {
self.entries = entries;
}
}
A small digression
Surely you’ve noticed the implementation of add_all()
is exactly the same in the three structs. Why did not we add blanket implementation of the add_all()
method in the trait?
Well, because we need access to the entries
field of the struct, and there’s no way to do that in Rust. Since I’m in love with Rust, I can rationalize this in several ways:
- First, the code duplication is not that a problem since there’s only one line of code.
- Second, the duplication is incidental. We could imagine using a
Set
instead of aVec
to store the entries, and the trait does not need to know about this. Ditto if we decide to rename the field. - Third, I can tell myself that this lacking feature is a good thing3 because I’ve often been bitten in other languages when sharing class members through inheritance (both in C++ and Python).
Take those how you want: I can tell myself those are good arguments, but you don’t have to believe me :)
The moral of the story
Here are my takeaways:
- When performance matters, don’t forget to measure it constantly, especially after refactorings (or even after each commit if you can afford to)
- The boiling frog metaphor is actually a good one, and you may be inside some boiling water without realizing it.
- And finally, listen to what people say to you when they tell you about something bad in your life. I actually felt something was off with my machine those last 6 months, but it took an other person to help me take a step back and understand what was wrong.
Take care and see you another time :)
I'd love to hear what you have to say, so please feel free to leave a comment below, or check out my contact page for more ways to get in touch with me.
-
That’s because I was using a tool named
z
before I decided to re-implement it myself. ↩ -
If you are wondering why, go read The Rule of Three on the Coding Horror blog. ↩
-
By the way, not all Rust users think this way. You can find a RFC about using fields in traits on GitHub. ↩
Oldest comments (1)
Great post. This hit me:
Benchmarks also serve as a proof when saying "this performs better than before".