1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
---
title: Overengineered search
date: 2026-01-03
layout: post
---
Developed a suffix-array-based search engine my personal site. While a simple
regex search was enough, couldn't resist the technical elegance of a proper
index.
Indexer: Indexer crawls the HTML, lowercases the text, and encodes it into
UTF-8 bytes. Null byte sentinel marks the document boundaries;
Lexicographically sorted 32-bit unsigned integer offsets are stored in sa.bin:
```
my @sa = 0 .. (length($corpus) - 1);
{
use bytes; # Force compare raw bytes
@sa = sort {
# First 64 bytes check (fast path)
(substr($corpus, $a, 64) cmp substr($corpus, $b, 64)) ||
# Full string fallback (required for correctness)
(substr($corpus, $a) cmp substr($corpus, $b))
} @sa;
}
```
32-bit offsets provide a 4 GB ceiling—overkill for a personal site, but
comforting to have.
O(L⋅N log N) sort is slow. 100 4.1 KB articles took 97.9s to index. L=64 fast
path reduces that to 1.31s (L=16, 32, 64: 1.29-1.31s; 128, 256: 1.33-1.35s).
Even with fast path optimization, indexer is unusable beyond 300 articles.
Search: Textbook range query with two binary searches, hosted in a FastCGI
process. Fixed-width offsets allow fast random access to the index:
```
seek($fh_sa, $mid * 4, 0);
read($fh_sa, my $bin_off, 4);
my $off = unpack("L", $bin_off);
seek($fh_cp, $off, 0);
read($fh_cp, my $text, $query_len);
```
Seek + read outperformed mmap for <1k files. At 10k, mmap was occasionally
faster (~200 µs), but consumed more memory—possibly due to OpenBSD’s VM
security trade-offs. Results may vary by OS.
Benchmarks: My articles have a 3.42 KB median, 3.43 KB mean, and 5.39 KB max.
Benchmarked on T490 (i7-10510U, OpenBSD 7.8, article size: 4.1 KB) against
linear regex search:
<pre class="pre-no-style">
=============================================================
SEARCH BENCHMARK: Suffix array vs. Linear regex
ARTICLE SIZE: 4.1 KB
=============================================================
100 files (Targeting: keyword_-1):
----------------+----------------------+---------------------
METRIC | SA | REGEX
----------------+----------------------+---------------------
Search time | 0.0009s | 0.0084s
Peak RAM | 7968 KB | 9676 KB
Indexing time | 1.3332s | N/A
Index size | 2070.38 KB | N/A
----------------+----------------------+---------------------
300 files (Targeting: keyword_-1):
----------------+----------------------+---------------------
METRIC | SA | REGEX
----------------+----------------------+---------------------
Search time | 0.0009s | 0.0242s
Peak RAM | 8024 KB | 9680 KB
Indexing time | 4.5658s | N/A
Index size | 6211.76 KB | N/A
----------------+----------------------+---------------------
5000 files (Targeting: keyword_-1):
----------------+----------------------+---------------------
METRIC | SA | REGEX
----------------+----------------------+---------------------
Search time | 0.0088s | 0.4937s
Peak RAM | 9948 KB | 11436 KB
Indexing time | 138.7510s | N/A
Index size | 103557.18 KB | N/A
----------------+----------------------+---------------------
</pre>
Security: httpd, slowcgi, Perl are in the OpenBSD base system. Used file system
permissions to govern access. Hardened the system by running it in chroot.
Resource exhaustion and XSS attacks are inherent. Limited concurrent searches
using lock-file semaphores, and capped the query length (64 B) and the result
set (20). Mitigated XSS by HTML-escaping all output using HTML::Escape.
Next release: Incremental indexing + SA-IS, Anno Domini 2076.
Commit: <a
href="https://git.asciimx.com/www/commit/?h=term&id=6da102d6e0494a3eac3f05fa3b2cdcc25ba2754e"
class="external" target="_blank" rel="noopener noreferrer">6da102d</a> |
Benchmarks: <a
href="https://git.asciimx.com/site-search-bm/commit/?id=f6d7c3fdbecbcb880c0c02fdffefa1f467c46b03"
class="external" target="_blank" rel="noopener noreferrer">f6d7c3f</a>
|
