FALCONN Library Documentation

FALCONN (FAst Lookups of Cosine and Other Nearest Neighbors) is a C++ library designed for efficient nearest neighbor search in high-dimensional spaces using Locality-Sensitive Hashing (LSH).

Key features include:

• Supported Similarity Metrics: Primarily optimized for cosine similarity using hyperplane LSH and cross polytope LSH families. It can also be used for Euclidean distance and maximum inner product search.
• Efficiency: Uses multi-probe LSH to minimize memory usage and is optimized for both dense and sparse data.
• Performance: On datasets with ~1 million points in ~100 dimensions, it typically achieves query times of a few milliseconds on modern desktop CPUs. It is particularly competitive in memory-constrained (low RAM) environments.
• Implementation: Written in C++ using templates to avoid runtime overhead. It leverages Eigen and FFHT for vectorized mathematical operations.

Google Test (gtest) is a portable C++ testing framework designed to work across Linux, Mac OS X, Windows, and embedded systems without requiring exceptions or RTTI.

Key advantages include:

• Nonfatal assertions (EXPECT_*): Allows tests to continue reporting multiple failures in a single cycle.
• Informative messages: Supports stream syntax for custom error messages, e.g., ASSERT_EQ(5, Foo(i)) << " where i = " << i;.
• Automatic test detection: No need to manually enumerate tests.
• Death tests: Verifies that production code triggers assertions under specific conditions.
• SCOPED_TRACE: Provides context for failures occurring inside loops or sub-routines.
• Test filtering: Allows running specific tests using name patterns.
• Extensibility: Supports custom predicates, custom type printing, and intercepting test events via a Service Provider Interface (SPI).

There are two ways to indicate a C++ inheritance relationship in pybind11:

1. Template Parameter: Specify the C++ base class as an extra template parameter in py::class_<Derived, Base>.
2. Python Parent Object: Assign the previously bound base class to a variable and pass it as the third argument to py::class_<Derived>(m, "Derived", base_object).

Polymorphism and Upcasting

• Non-polymorphic types: If you return a base pointer to a derived instance (e.g., std::unique_ptr<Base>), Python will only see the Base type. It will not automatically upcast to the derived type, and derived methods will be inaccessible.
• Polymorphic types: If the C++ class has at least one virtual function, pybind11 performs automatic upcasting. When a base pointer is returned, Python identifies the actual concrete derived type, providing access to all derived functions and attributes.

// Polymorphic setup
struct PolymorphicPet {
    virtual ~PolymorphicPet() = default;
};

struct PolymorphicDog : PolymorphicPet {
    std::string bark() const { return "woof!"; }
};

py::class_<PolymorphicPet>(m, "PolymorphicPet");
py::class_<PolymorphicDog, PolymorphicPet>(m, "PolymorphicDog")
    .def(py::init<>())
    .def("bark", &PolymorphicDog::bark);

// Method 1: Template parameter
py::class_<Dog, Pet>(m, "Dog")
    .def(py::init<const std::string &>());

// Method 2: Pass parent class_ object
py::class_<Pet> pet(m, "Pet");
py::class_<Dog>(m, "Dog", pet)
    .def(py::init<const std::string &>());

You can mock non-virtual methods by creating an unrelated mock class that has the same method signatures as the real class. This is used for 'hi-perf dependency injection' where you avoid the overhead of virtual functions.

Because the classes are unrelated and methods are non-virtual, you must choose which class to use at compile time, typically by templatizing the consumer code.

// Production class (no virtual methods)
class ConcretePacketStream {
 public:
  void AppendPacket(Packet* new_packet);
};

// Mock class (unrelated to ConcretePacketStream)
class MockPacketStream {
 public:
  MOCK_CONST_METHOD1(GetPacket, const Packet*(size_t packet_number));
};

// Consumer code using templates to switch implementations
template <class PacketStream>
void CreateConnection(PacketStream* stream) { ... }

// In tests:
MockPacketStream mock_stream;
CreateConnection<MockPacketStream>(&mock_stream);

By default, pybind11 bindings are "global," meaning a type defined in one module can be returned from any other module as the same Python type. While useful for splitting libraries, this causes ImportError: generic_type: type "X" is already registered! if two different modules attempt to bind the same external C++ class differently.

To resolve this, use the py::module_local() attribute in the py::class_ constructor. This makes the binding specific to that module, resulting in distinct Python classes (e.g., module1.Pet and module2.Pet) even if they represent the same C++ type.

Key Behaviors of py::module_local():

1. Directionality: Locality only applies to the C++ $\rightarrow$ Python direction. When passing a module-local type into a C++ function, the underlying C++ type is still recognized.
2. Casting: Within the module where the local binding exists, C++ instances will be cast to the local Python type. In other modules, they will be converted to the global Python type if a global binding exists.
3. Isolation: From the Python perspective, module1.Pet and module2.Pet are distinct classes.

// In module A, bind an external class locally to avoid conflicts
py::class<external_type>(m, "ExternalType", py::module_local())
    .def("method", &external_type::method);