khala is a fast, cross-platform launcher/finder.
Compared to most launchers, khala does not require a daemon or use a retained index. It only does work when you tell it to.
This avoids the background CPU and disk I/O of continuous indexing and keeps ranking deterministic: the same query on the same filesystem state yields the same results.
A streaming architecture allows khala to stay snappy despite this constraint by searching file paths as they are being scanned.
On my Linux laptop, the entire rootfs with ~1.5M files is scanned in ~1 second.
Fuzzy searching the scanned file paths uses SIMD optimized scoring functions.
Next to finding files, khala offers utility actions similar to command palette interfaces known from IDEs like VS Code.
Both file and utility actions can be extended with custom commands using your scripting language of choice.
Further configuration includes search scope via white and blacklists, as well as customizing appearance with fonts and color themes.
khala is implemented using native graphics APIs and currently supports Linux (X11 or Wayland) and Windows.
This results in minimal launch overhead due to small executable size and minimal dependencies.
Platform note: Filesystem scanning is significantly slower on Windows file systems. For this reason, khala can be configured to run as a background process, which is also required to register a global launch hotkey on Windows.
Streaming Architecture
The initial plan was to split the launcher into a scanning daemon and the actual launcher. After experimenting and measuring the scanning and fuzzy searching performance, it turns out cold-starting the launcher every time is feasible.
The main idea that makes cold starting viable is streaming file paths from the file system scanner through the fuzzy scoring and ranking workers to the UI as they become available. Search queries run against whatever has been scanned so far, so typing can start immediately and results update as the scan progresses.
Scanned file paths are collected into chunks. After reaching the configured CHUNK_SIZE, ownership of the chunk is passed to the StreamingIndex, a mutex guarded queue.
class StreamingIndex
{
public:
void add_chunk(PackedStrings &&chunk);
[[nodiscard]] size_t get_available_chunks() const;
[[nodiscard]] std::shared_ptr<const PackedStrings> get_chunk(size_t chunk_index) const;
void wait_for_new_chunks(size_t known_chunks) const;
private:
std::vector<std::shared_ptr<const PackedStrings>> chunks_;
mutable std::mutex mutex_;
mutable std::condition_variable chunk_available_;
};
The StreamingRanker polls the StreamingIndex to view chunks as they become available. File paths in the available chunks are scored against the current query and merged with the existing top n results.
On changes to the top-n results, a ResultUpdate is atomically passed to the UI via the LastWriterWinsSlot.
File system scanning
The main thread launches scan_filesystem_streaming() which recursively scans the configured root directories to collect a number of disjoint filesystem subtrees, which represent independent work units.
These are then distributed to worker threads which scan their assigned subtrees and write all full paths to chunks, which are implemented as flat string arrays (PackedString) to avoid frequent allocations.
void scan_filesystem_streaming(const std::set<fs::path> &root_paths,
StreamingIndex &index,
const std::set<fs::path> &ignore_dirs,
const std::set<std::string> &ignore_dir_names)
{
std::deque<fs::path> to_expand;
// Initialize with all root paths
PackedStrings root_files;
for (const auto &root_path : root_paths) {
to_expand.push_back(fs::canonical(root_path));
}
const auto min_work_units = std::thread::hardware_concurrency() * 4;
while (!to_expand.empty() && to_expand.size() < min_work_units) {
const auto path = to_expand.front();
to_expand.pop_front();
for (const auto &entry : fs::directory_iterator(path)) {
if (entry.is_directory()) {
if (ignore_dir_names.contains(platform::path_to_string(
entry.path().filename())) ||
ignore_dirs.contains(entry.path())) {
continue;
}
to_expand.push_back(entry.path());
} else if (entry.is_regular_file()) {
platform::push_path(root_files, entry.path());
}
}
}
// Add root files as first chunk
if (!root_files.empty()) {
index.add_chunk(std::move(root_files));
}
std::vector<fs::path> work_units(to_expand.cbegin(), to_expand.cend());
std::atomic<size_t> next_dir{0};
std::vector<std::thread> workers;
const size_t num_threads =
std::min(work_units.size(),
static_cast<size_t>(std::thread::hardware_concurrency()));
for (size_t i = 0; i < num_threads; i++) {
workers.emplace_back([&]() {
for (;;) {
const size_t idx =
next_dir.fetch_add(1, std::memory_order_relaxed);
if (idx >= work_units.size())
break;
scan_subtree_streaming(work_units[idx], ignore_dirs,
ignore_dir_names, index);
}
});
}
for (auto &w : workers) {
w.join();
}
}
StreamingRanker
The ranker is where most of the work happens. It
- watches for new chunks
- scores all file paths in each chunk against the current query
- maintains top-n results across all processed chunks
- pushes updates to the UI
When the query changes, all chunks are reprocessed. When only the result count increases, for example when the user scrolls through results, existing scores can be reused and the top-n results are expanded.
The scoring itself is parallelized across chunks. I implemented parallel::parallel_for myself to avoid the tbb dependency incurred by std::execution and the OpenMP runtime dependency for #pragma omp parallel for. Benchmarks showed that on the platforms I have available, both options perform similar to naive thread spawns.
Each worker thread gets a chunk and a thread-local result vector. After parallel scoring, results are sequentially merged into a min heap.
// Each thread gets its own results vector
std::vector<std::vector<StreamingRankResult>> thread_local_results(chunks_to_process);
parallel::parallel_for(
processed_chunks_, available_chunks, [&](size_t chunk_idx) {
auto chunk = streaming_index_.get_chunk(chunk_idx);
assert(chunk);
const auto chunk_size = chunk->size();
auto &local_results =
thread_local_results[chunk_idx - processed_chunks_];
local_results.reserve(chunk_size /
4); // estimate ~25% match rate
for (uint16_t i = 0; i < chunk_size; ++i) {
const auto score = fuzzy::fuzzy_score_5_simd(
chunk->at(i), current_request_.query);
if (score > 0.0F) {
local_results.push_back(StreamingRankResult{
.chunk_idx = static_cast<uint16_t>(chunk_idx),
.local_idx = i,
.score = score,
});
}
}
});
// Sequential merge
const size_t effective_cap =
std::max(RANKING_HEAP_CAPACITY, current_request_.requested_count);
for (auto &thread_local_result : thread_local_results) {
processed_string_count += thread_local_result.size();
for (auto result : thread_local_result) {
constexpr auto MinHeapCmp = std::greater<StreamingRankResult>{};
if (top_results_.size() < effective_cap) {
top_results_.push_back(result);
std::push_heap(top_results_.begin(), top_results_.end(),
MinHeapCmp);
} else if (result.score > top_results_.front().score) {
std::pop_heap(top_results_.begin(), top_results_.end(),
MinHeapCmp);
top_results_.back() =
result; // Overwrite lowest scoring RankResult
std::push_heap(top_results_.begin(), top_results_.end(),
MinHeapCmp);
}
}
}