Bm25er - Search local files like you're searching the web (BM25 implementation)

[shayan15sa]

bm25er

An implementation of Okapi BM25 alogrithm in zig for searching local files. The main reason I started this project is learning zig. It has been a fun experience so far. It really is a breath of fresh air compared to java homework I have to do. Coming from C, I can totally see and appreciate the benefits it provides.

Main Inspiration: https://www.youtube.com/watch?v=hm5xOJiVEeg

Github repo: GitHub - shayan15sa/bm25er · GitHub

I’d really apprentice any comments on the code. I am sure that I am not doing many things the zig way.

Supported Zig versions

I compile the project with the zig 0.16 and I think because of the Io changes It won’t compile on the zig 0.15 (I’m not sure though).

[splinterofchaos]

@shayan15sa

I’d really apprentice any comments on the code. I am sure that I am not doing many things the zig way.

Hey! I did try it out and took a look at the code. Overall, I think your code is very reasonable. It could be improved a few ways, but mostly I want to talk about some of the bigger issues I had.

    const search_keyword = if (args.len > 1) args[1] else std.process.exit(1);

When I cloned the repo, the first thing I tried was $ zig build run and the error message I got back didn’t help me understand what went wrong. I changed it to this for my convenience:

    const search_keyword = if (args.len > 1) args[1] else {
        std.debug.print("usage: bm25er PATTERN [DIRECTORY]\n", .{});
        std.process.exit(1);
    };

Second issue:

$ zig build run -- bm25
File zig-out/bin/bm25er is too big abbasthread 256656 panic: reached unreachable code

First problem is that “File zig-out/bin/bm25er is too big abbas” needs a \n at the end. Second:

        //TODO: replace 512 with something smaller when the tokenizer is fixed and also supports html. You can check the len and if it exceeds the array size allocate on arena too.
        var tok_buffer: [512]u8 = undefined;
        const tok_lower = std.ascii.lowerString(&tok_buffer, tok);

The error came from lowerString() because there’s no protection against reading binary files and in some of them tok is larger than 512. Since you own the memory under tok, you could actually avoid the buffer here and modify the source directly. Or, if you do want to keep them separate, please add a check here.

const f = std.Io.Dir.readFileAlloc(dir, io, file_name, gpa, .limited(1_000_000)) 

When I tried to scan one of my repos, a header file imported by raylib was too large. readFileAlloc() is a nice convenient function, and I agree with your decision to limit the amount of memory this consumes, but since you don’t know the size of the files in advance and need to read many files, a better way is to set aside a sufficiently large buffer (ex: 4096) and do buffered reads without allocation.

example using the reader interface: Zig Cookbook

On binary files: I’ve heard of a technique for detecting if you’re reading a binary file where you check the first 128 or so bytes to see if they’re all valid, printable characters. As far as I know there isn’t support in the standard for non-ASCII but just checking std.ascii.isAscii() would be okay.

[vincentd]

First thing I noticed:

lenght: u32

Doesn’t affect the logic, but it still hurts to see it.

Some parts have way too much going on in a single line. For example:

return @log(1 + (((@as(f32, @floatFromInt(doc_counter)) - @as(f32, @floatFromInt(n)) + 0.5) / (@as(f32, @floatFromInt(n)) + 0.5))));

Good practice is to break it up into simpler calculations. It’s easier to read, and it’s obvious which calculations happen before other ones.

const a: f32 = @as(f32, @floatFromInt(doc_counter));
const b: f32 = @as(f32, @floatFromInt(n));
const c: f32 = @as(f32, @floatFromInt(n));
const d: f32 = (a - b + 0.5) /  (c + 0.5);
return @log(1 + d);

Note: a/b/c/d are for example, you should try to use names that help describe what the equation is doing in each step.

It’s easier to see patterns this way, so you can simplify the equation:

const a: f32 = @as(f32, @floatFromInt(doc_counter));
const b: f32 = @as(f32, @floatFromInt(n));
const d: f32 = (a - b + 0.5) /  (b + 0.5);
return @log(1 + d);

You can also remove the @as() as it can now infer the type from the variable:

const a: f32 = @floatFromInt(doc_counter);
const b: f32 = @floatFromInt(n);
const d: f32 = (a - b + 0.5) /  (b + 0.5);
return @log(1 + d);

Easier to read, easier to modify, and you can add comments next to each step!

Also, if one of the operations causes an error at runtime it’s easier to find what’s causing it, because the line numbers are different.

.

@splinterofchaos

On binary files: I’ve heard of a technique for detecting if you’re reading a binary file where you check the first 128 or so bytes to see if they’re all valid, printable characters. As far as I know there isn’t support in the standard for non-ASCII but just checking std.ascii.isAscii() would be okay.

I believe the way grep does it is by scanning the first buffer-load (e.g 32kB) it reads for null characters, or invalid UTF-8 encoding (e.g. overlong characters)

I think you could use the functions in std.unicode to do that. I might give that a try actually - I have a crude zig version of grep which I made as an example in a library.

EDIT:

This seems to work - for zig-0.16.0

/// First ensures the buffer is full (or EOF), then returns true
/// if the buffer consists entirely of UTF-8 codepoints.
///
/// Useful for distinguishing text files from binary files.
fn checkFileIsValidUtf8(reader: *std.Io.Reader) Io.Reader.Error!bool {
    const peek = reader.peek(reader.buffer.len) catch |err|
        switch (err) {
            Io.Reader.Error.EndOfStream => try reader.peekGreedy(0),
            else => return err,
        };
    // std.log.debug("Checking utf-8 validity for first {} bytes", .{peek.len});
    return std.unicode.utf8ValidateSlice(peek);
}

[shayan15sa]

First of all, thank you so much for the time you spent writing the comment.

@splinterofchaos

When I cloned the repo, the first thing I tried was $ zig build run and the error message I got back didn’t help me understand what went wrong. I changed it to this for my convenience:

I meant to add proper help and error messages before posting the project here. Sorry about that.

@splinterofchaos

Since you own the memory under tok, you could actually avoid the buffer here and modify the source directly.

I looked at the source code of lowerString() and it seems that it uses a normal for loop for rewriting on the memory. So as you mentioned it should be ok to replace it directly. But my main question is that if I replace the readFileAlloc() with the buffered reader, would this approach still be viable? (my guess is that, it still should be fine but I’m not sure).

@splinterofchaos

On binary files: I’ve heard of a technique for detecting if you’re reading a binary file where you check the first 128 or so bytes to see if they’re all valid, printable characters. As far as I know there isn’t support in the standard for non-ASCII but just checking std.ascii.isAscii() would be okay.

I actually just tested it on my markdown files. I didn’t notice this problem. I will add a fix based on the example provided by @vincentd (thanks!)

[shayan15sa]

Thanks for taking the time to go through the code.

@vincentd

lenght: u32

Doesn’t affect the logic, but it still hurts to see it.

Sorry about that!

@vincentd

Good practice is to break it up into simpler calculations. It’s easier to read, and it’s obvious which calculations happen before other ones.

Yes, you are completely right about this. I will definitely break it up. I have a question, though: will doing this change the generated assembly or affect performance in any way? I know these things probably won’t have a significant impact on performance, but I’m just curious.

@vincentd

I believe the way grep does it is by scanning the first buffer-load (e.g. 32kB) it reads for null characters, or invalid UTF-8 encoding (e.g. overlong characters)

I will definitely add this feature as soon as I have some free time. Thank you for the example!

[vincentd]

@shayan15sa

Yes, you are completely right about this. I will definitely break it up. I have a question, though: will doing this change the generated assembly or affect performance in any way? I know these things probably won’t have a significant impact on performance, but I’m just curious.

Short answer: It depends.

The generated assembly could be:

• Shorter, because there’s less individual calculations being done.
• Exactly the same length, because clever people designed the compiler to ‘optimize out’ computations when it can tell they are unnecessary.
• Longer, because even very clever people make mistakes sometimes.

The only way to know for sure is to look at the output of the compiler. You can also use compiler explorer if it’s easier.

As for performance, it has zero effect. The performance on a modern processor is dominated by:

1. Memory access patterns (a.k.a. cache misses)
2. Parallelisation.
3. Conflicts in memory shared by different threads.
4. How many syscalls you make.

This series of articles is great if you want to learn why the first 3 matter: What every programmer should know about memory, Part 1 [LWN.net]

Number 4 is the reason why when reading/writing to a file, a large buffer gives you better performance than a small one.

[splinterofchaos]

@shayan15sa

But my main question is that if I replace the readFileAlloc() with the buffered reader, would this approach still be viable?

Yeah, nothing changes there, just where the buffer comes from.

[splinterofchaos]

@vincentd

I believe the way grep does it is by scanning the first buffer-load (e.g 32kB) it reads for null characters, or invalid UTF-8 encoding (e.g. overlong characters)

lol, that sucks. I used to add literal null characters into my C++ files for fun, since I learned this is technically possible. I just tested and ag can’t find those files!