Implement support for larger basevals in TurboPFor.

[plocate] / plocate-build.cpp

diff --git a/plocate-build.cpp b/plocate-build.cpp
index b409bb820645f00dd1e3ab58857c7c0a8225a519..023aedb53339da12b0e5487f662d5193fca6943f 100644 (file)
--- a/plocate-build.cpp
+++ b/plocate-build.cpp
@@ -1,21 +1,20 @@
 #include "db.h"
-#include "vp4.h"
+#include "turbopfor-encode.h"
 
 #include <algorithm>
-#include <arpa/inet.h>
 #include <assert.h>
 #include <chrono>
-#include <endian.h>
-#include <fcntl.h>
+#include <iosfwd>
 #include <math.h>
 #include <memory>
+#include <stdint.h>
 #include <stdio.h>
+#include <stdlib.h>
 #include <string.h>
 #include <string>
+#include <string_view>
 #include <sys/stat.h>
-#include <sys/types.h>
-#include <unistd.h>
-#include <unordered_map>
+#include <utility>
 #include <vector>
 #include <zstd.h>
 
@@ -72,7 +71,7 @@ struct db_directory {
 
 class PostingListBuilder {
 public:
-       void add_docid(uint32_t docid);
+       inline void add_docid(uint32_t docid);
        void finish();
 
        string encoded;
@@ -82,7 +81,7 @@ private:
        void write_header(uint32_t docid);
        void append_block();
 
-       vector<uint32_t> pending_docids;
+       vector<uint32_t> pending_deltas;
 
        uint32_t last_block_end, last_docid = -1;
 };
@@ -102,11 +101,11 @@ void PostingListBuilder::add_docid(uint32_t docid)
                return;
        }
 
+       pending_deltas.push_back(docid - last_docid - 1);
        last_docid = docid;
-       pending_docids.push_back(docid);
-       if (pending_docids.size() == 128) {
+       if (pending_deltas.size() == 128) {
                append_block();
-               pending_docids.clear();
+               pending_deltas.clear();
                last_block_end = docid;
        }
        ++num_docids;
@@ -114,7 +113,7 @@ void PostingListBuilder::add_docid(uint32_t docid)
 
 void PostingListBuilder::finish()
 {
-       if (pending_docids.empty()) {
+       if (pending_deltas.empty()) {
                return;
        }
 
@@ -122,38 +121,50 @@ void PostingListBuilder::finish()
 
        // No interleaving for partial blocks.
        unsigned char buf[P4NENC_BOUND(128)];
-       unsigned char *end = p4d1enc32(pending_docids.data(), pending_docids.size(), buf, last_block_end);
+       unsigned char *end = encode_pfor_single_block<128>(pending_deltas.data(), pending_deltas.size(), /*interleaved=*/false, buf);
        encoded.append(reinterpret_cast<char *>(buf), reinterpret_cast<char *>(end));
 }
 
 void PostingListBuilder::append_block()
 {
        unsigned char buf[P4NENC_BOUND(128)];
-       assert(pending_docids.size() == 128);
-       unsigned char *end = p4d1enc128v32(pending_docids.data(), 128, buf, last_block_end);
+       assert(pending_deltas.size() == 128);
+       unsigned char *end = encode_pfor_single_block<128>(pending_deltas.data(), 128, /*interleaved=*/true, buf);
        encoded.append(reinterpret_cast<char *>(buf), reinterpret_cast<char *>(end));
 }
 
 void PostingListBuilder::write_header(uint32_t docid)
 {
        unsigned char buf[P4NENC_BOUND(1)];
-       size_t bytes = p4nd1enc128v32(&docid, 1, buf);
-       encoded.append(reinterpret_cast<char *>(buf), bytes);
+       unsigned char *end = write_baseval(docid, buf);
+       encoded.append(reinterpret_cast<char *>(buf), end - buf);
 }
 
 class Corpus {
 public:
        Corpus(FILE *outfp, size_t block_size)
-               : invindex(new PostingListBuilder*[NUM_TRIGRAMS]), outfp(outfp), block_size(block_size) {}
+               : invindex(new PostingListBuilder *[NUM_TRIGRAMS]), outfp(outfp), block_size(block_size)
+       {
+               fill(invindex.get(), invindex.get() + NUM_TRIGRAMS, nullptr);
+       }
+       ~Corpus()
+       {
+               for (unsigned i = 0; i < NUM_TRIGRAMS; ++i) {
+                       delete invindex[i];
+               }
+       }
+
        void add_file(string filename);
        void flush_block();
 
        vector<uint64_t> filename_blocks;
        size_t num_files = 0, num_files_in_block = 0, num_blocks = 0;
-       bool seen_trigram(uint32_t trgm) {
+       bool seen_trigram(uint32_t trgm)
+       {
                return invindex[trgm] != nullptr;
        }
-       PostingListBuilder& get_pl_builder(uint32_t trgm) {
+       PostingListBuilder &get_pl_builder(uint32_t trgm)
+       {
                if (invindex[trgm] == nullptr) {
                        invindex[trgm] = new PostingListBuilder;
                }
@@ -161,7 +172,7 @@ public:
        }
 
 private:
-       unique_ptr<PostingListBuilder*[]> invindex;
+       unique_ptr<PostingListBuilder *[]> invindex;
        FILE *outfp;
        string current_block;
        string tempbuf;
@@ -217,7 +228,7 @@ void Corpus::flush_block()
 string read_cstr(FILE *fp)
 {
        string ret;
-       for ( ;; ) {
+       for (;;) {
                int ch = getc(fp);
                if (ch == -1) {
                        perror("getc");
@@ -362,6 +373,7 @@ void do_build(const char *infile, const char *outfile, int block_size)
        hdr.version = -1;  // Mark as broken.
        hdr.hashtable_size = 0;  // Not known yet.
        hdr.extra_ht_slots = num_overflow_slots;
+       hdr.num_docids = 0;
        hdr.hash_table_offset_bytes = -1;  // We don't know these offsets yet.
        hdr.filename_index_offset_bytes = -1;
        fwrite(&hdr, sizeof(hdr), 1, outfp);
@@ -402,7 +414,8 @@ void do_build(const char *infile, const char *outfile, int block_size)
        size_t trigrams = 0, longest_posting_list = 0;
        size_t bytes_for_posting_lists = 0;
        for (unsigned trgm = 0; trgm < NUM_TRIGRAMS; ++trgm) {
-               if (!corpus.seen_trigram(trgm)) continue;
+               if (!corpus.seen_trigram(trgm))
+                       continue;
                PostingListBuilder &pl_builder = corpus.get_pl_builder(trgm);
                pl_builder.finish();
                longest_posting_list = max(longest_posting_list, pl_builder.num_docids);