Improve perf for compile dbs in large projects

When using a compilation database (compile_commands.json) in very large
projects, significant delays would occur when changing files --
particularly those that happened to be far down the db. Rather than
iterating over the whole list every time, we now build up a lookup table
based on the tail of the filename (and tail of the directory for
widening searches) and iterate over the much smaller list of compile
commands for files with the given name.

Test metrics (from compile_database_perf/test.sh) show a 90% performance
improvement -- from 25 seconds to 2.5 seconds per run.

1 files changed, 29 insertions, 0 deletions

diff --git a/test/compile_database_perf/test.sh b/test/compile_database_perf/test.sh
new file mode 100755
index 00000000..15a2b442
--- /dev/null
+++ b/test/compile_database_perf/test.sh
@@ -0,0 +1,29 @@
+#!/bin/bash
+
+# Generate source files for ALE to read. They don't have to be very long, the delay is in reading compile_commands, not actually running tests
+mkdir -p gen_src
+for i in {1..400}; do echo "const char *GeneratedFunc${i}() { return \"Word ${i}\"; }" > gen_src/source${i}.cpp; done
+
+# Create the compile_commands database
+echo "[ {" > compile_commands.json
+
+for i in {1..399}; do 
+  {
+    echo "\"command\": \"clang++ -c $(pwd)/gen_src/source${i}.cpp -o $(pwd)/build/obj/Debug/source${i}.o -MF $(pwd)/build/obj/Debug/source${i}.d -MMD -MP\","
+    echo "\"directory\": \"$(pwd)/build\","
+    echo "\"file\": \"$(pwd)/gen_src/source${i}.cpp\""
+    echo "}, {"
+  } >> compile_commands.json
+done
+
+{
+  echo "\"command\": \"clang++ -c $(pwd)/gen_src/source400.cpp -o $(pwd)/build/obj/Debug/source400.o -MF $(pwd)/build/obj/Debug/source400.d -MMD -MP\","
+  echo "\"directory\": \"$(pwd)/build\","
+  echo "\"file\": \"$(pwd)/gen_src/source400.cpp\""
+  echo "} ]"
+} >> compile_commands.json
+
+# Start up vim and switch back and forth between files -- at least one of the files must be near the bottom of compile_commands.json
+time vim -c "for i in range(0,20) | edit gen_src/source10.cpp | edit gen_src/source400.cpp | endfor" \
+  -c "noautocmd qa!" \
+  `find . | grep "source..\.cpp"`