In the searchable list we filtered with includes, and debounced the typing so we wouldn't filter on every keystroke. Let's replace both with a fuzzy search written in C++, as a C++ Turbo Module: srchlst finds "Searchable list", and the results arrive in the same frame as the key.
## Why C++ here
The battery module was a poor fit for C++: it calls platform APIs, so the code was different on each side anyway. A fuzzy matcher is the opposite:
- It is pure computation: no platform API, so one file serves iOS and Android.
- It is a tight loop over thousands of strings, run on every keystroke. Compiled ahead of time, it allocates nothing per character and gives the garbage collector nothing to do.
- A C++ Turbo Module is called through JSI, synchronously.
searchreturns an array, not a promise, so there is no frame to wait.
JavaScript is fast too. Measure on your list and your slowest device first; if filter keeps up, keep it.
## The shape
In a React Native app, trimmed to what matters here:
specs/NativeFuzzy.ts
package.json
shared/NativeFuzzy.h
shared/NativeFuzzy.cpp
android/app/build.gradle
android/app/src/main/jni/CMakeLists.txt
android/app/src/main/jni/OnLoad.cpp
ios/NativeFuzzyProvider.h
ios/NativeFuzzyProvider.mm## The spec
The list crosses into C++ once, with setItems. Each keystroke then sends only the query, and gets back the indexes of the best matches:
import type { TurboModule } from 'react-native';
import { TurboModuleRegistry } from 'react-native';
export interface Spec extends TurboModule {
readonly setItems: (items: string[]) => void;
readonly search: (query: string, limit: number) => number[];
}
export default TurboModuleRegistry.getEnforcing<Spec>('NativeFuzzy');{
"codegenConfig": {
"name": "AppSpecs",
"type": "modules",
"jsSrcsDir": "specs",
"android": { "javaPackageName": "com.fuzzyapp.specs" },
"ios": { "modulesProvider": { "NativeFuzzy": "NativeFuzzyProvider" } }
}
}## C++
Codegen writes NativeFuzzyCxxSpec, a template the module extends. Its methods take the JavaScript runtime first, then the spec's arguments as C++ types: string[] arrives as a std::vector<std::string>, and a std::vector<int> goes back as an array of numbers:
#pragma once
#include <AppSpecsJSI.h>
#include <memory>
#include <string>
#include <vector>
namespace facebook::react {
class NativeFuzzy : public NativeFuzzyCxxSpec<NativeFuzzy> {
public:
explicit NativeFuzzy(std::shared_ptr<CallInvoker> jsInvoker);
void setItems(jsi::Runtime& rt, std::vector<std::string> items);
std::vector<int> search(jsi::Runtime& rt, std::string query, int limit);
private:
std::vector<std::string> items_;
};
} // namespace facebook::reactThe matcher walks each item once, looking for the query's letters in order. A letter scores more when it follows the previous match, and more again at the start of a word; a long item loses a little, so "List" beats "A long list of settings":
#include "NativeFuzzy.h"
#include <algorithm>
#include <utility>
namespace facebook::react {
namespace {
// ASCII lower case; other bytes pass through, so UTF-8 still matches itself.
char lower(char c) {
return c >= 'A' && c <= 'Z' ? static_cast<char>(c + ('a' - 'A')) : c;
}
bool startsWord(const std::string& text, size_t i) {
if (i == 0) return true;
char before = text[i - 1];
return before == ' ' || before == '-' || before == '_' || before == '/';
}
// The query's letters in the item, in order: a score, or -1 when one is missing.
int score(const std::string& query, const std::string& item) {
int total = 0;
int streak = 0;
size_t found = 0;
for (size_t i = 0; i < item.size() && found < query.size(); i++) {
if (lower(item[i]) != query[found]) {
streak = 0;
continue;
}
streak++;
total += 1 + 2 * streak + (startsWord(item, i) ? 8 : 0);
found++;
}
if (found < query.size()) return -1;
return total - static_cast<int>(item.size() / 8);
}
} // namespace
NativeFuzzy::NativeFuzzy(std::shared_ptr<CallInvoker> jsInvoker)
: NativeFuzzyCxxSpec(std::move(jsInvoker)) {}
void NativeFuzzy::setItems(jsi::Runtime&, std::vector<std::string> items) {
items_ = std::move(items);
}
std::vector<int> NativeFuzzy::search(jsi::Runtime&, std::string query, int limit) {
std::string q;
q.reserve(query.size());
for (char c : query) {
if (c != ' ') q.push_back(lower(c));
}
// (score, index) for every item that has all the letters.
std::vector<std::pair<int, int>> hits;
hits.reserve(items_.size());
for (int i = 0; i < static_cast<int>(items_.size()); i++) {
int s = score(q, items_[i]);
if (s >= 0) hits.emplace_back(s, i);
}
// Only the best `limit` are sorted: a short screen of a long list costs little.
auto count = std::min(hits.size(), static_cast<size_t>(std::max(limit, 0)));
std::partial_sort(hits.begin(), hits.begin() + count, hits.end(), [](const auto& a, const auto& b) {
return a.first != b.first ? a.first > b.first : a.second < b.second;
});
std::vector<int> best;
best.reserve(count);
for (size_t k = 0; k < count; k++) best.push_back(hits[k].second);
return best;
}
} // namespace facebook::reactThe matcher is greedy: it takes each letter's first occurrence, which is fast and good enough for a list of names. Every call runs on the JavaScript thread, so items_ needs no lock.
## Android
Gradle builds the C++ through CMake. build.gradle points at the CMake file:
android {
externalNativeBuild {
cmake {
path "src/main/jni/CMakeLists.txt"
}
}
}The CMake file adds shared/ to the library React Native already builds for the app:
cmake_minimum_required(VERSION 3.13)
project(appmodules)
include(${REACT_ANDROID_DIR}/cmake-utils/ReactNative-application.cmake)
target_sources(${CMAKE_PROJECT_NAME} PRIVATE ../../../../../shared/NativeFuzzy.cpp)
target_include_directories(${CMAKE_PROJECT_NAME} PUBLIC ../../../../../shared)OnLoad.cpp is copied from React Native's template for your version. Only its C++ module provider changes, to hand out the module by name:
#include <NativeFuzzy.h>
std::shared_ptr<TurboModule> cxxModuleProvider(
const std::string& name,
const std::shared_ptr<CallInvoker>& jsInvoker) {
if (name == NativeFuzzy::kModuleName) {
return std::make_shared<NativeFuzzy>(jsInvoker);
}
return autolinking_cxxModuleProvider(name, jsInvoker);
}No Kotlin at all.
## iOS
Xcode compiles shared/ once the folder is added to the app's target. A small provider, named in package.json, creates the module:
#import <Foundation/Foundation.h>
#import <ReactCommon/RCTTurboModule.h>
NS_ASSUME_NONNULL_BEGIN
@interface NativeFuzzyProvider : NSObject <RCTModuleProvider>
@end
NS_ASSUME_NONNULL_END#import "NativeFuzzyProvider.h"
#import <ReactCommon/CallInvoker.h>
#import <ReactCommon/TurboModule.h>
#import "NativeFuzzy.h"
@implementation NativeFuzzyProvider
- (std::shared_ptr<facebook::react::TurboModule>)getTurboModule:
(const facebook::react::ObjCTurboModule::InitParams &)params {
return std::make_shared<facebook::react::NativeFuzzy>(params.jsInvoker);
}
@endNo Swift either: the two files are glue, and the search is the same C++ on both platforms.
## TypeScript
The hook hands the titles over when the list changes, and searches while rendering. search is synchronous, so the debounce from the searchable list can go:
import { useMemo } from 'react';
import NativeFuzzy from './specs/NativeFuzzy';
type Item = { id: string; title: string };
export function useFuzzy(items: Item[], query: string, limit = 50): Item[] {
// setItems only replaces the list, so running it again for the same items is harmless.
const loaded = useMemo(() => {
NativeFuzzy.setItems(items.map((item) => item.title));
return items;
}, [items]);
return useMemo(
() => (query.trim() ? NativeFuzzy.search(query, limit).map((i) => loaded[i]) : loaded),
[loaded, query, limit],
);
}The module keeps one list. That is all this screen needs; two screens searching at once would want a list per id.
In SearchScreen, the useDebounced and useMemo lines become one:
const visible = useFuzzy(items, state.query);## Run it
Codegen runs at pod install and in Gradle, so the C++ spec header exists before the C++ is compiled:
cd ios && bundle exec pod install && cd ..
npx react-native run-ios
npx react-native run-androidC++ earns its place when the work is computation, the same on every platform, and called often enough that a frame matters. For anything that talks to the platform, Swift and Kotlin stay the better tools. The React Native docs on C++ Turbo Native Modules cover more types, including custom ones.