Given a list of posts, compute the top 5 related posts for each post based on the number of shared tags.
- Read the posts JSON file.
- Iterate over the posts and populate a map containing:
tag -> List<int>, with the int representing the post index of each post with that tag. - Iterate over the posts and for each post:
- Create a map:
PostIndex -> intto track the number of shared tags - For each tag, Iterate over the posts that have that tag
- For each post, increment the shared tag count in the map.
- Create a map:
- Sort the related posts by the number of shared tags.
- Write the top 5 related posts for each post to a new JSON file.
./run.sh go | rust | python | all
# windows (powershell)
./run.ps1 go | rust | python | all
or
pwsh ./run.ps1 go | rust | python | all
Rules
- FFI (including assembly inlining)
- Unsafe code blocks
- Custom benchmarking
- Disabling runtime checks (bounds etc)
- Specific hardware targeting
- Support up to 100,000 posts
- Parse json at runtime
- Not hardcode number of posts
- Support up to 100 tags
- Use a stable release of the compiler/runtime
- Represent tags as strings
Updated Results from github workflow (raw data)
VM Specs
NB: The benchmark runs on the free tier of github workflow.- CPU: 2 vCPUs
- RAM: 7GB
- OS: Ubuntu 22.04
| Language | Processing Time | Total (PT + I/O) |
|---|---|---|
| Go | 25.59 ms | 55.0 ms |
| Rust | 30.93 ms | 47.7 ms |
| Zig | 38.00 ms | 65.0 ms |
| Nim | 39.07 ms | 65.3 ms |
| Julia | 39.93 ms | 3.404 s |
| Java (GraalVM) | 40.00 ms | 69.6 ms |
| F# | 49.87 ms | 295.5 ms |
| Odin | 53.73 ms | 299.7 ms |
| Vlang | 58.53 ms | 382.7 ms |
| Swift | 64.48 ms | 437.8 ms |
| Crystal | 68.37 ms | 120.9 ms |
| C# | 79.72 ms | 141.0 ms |
| Dart VM | 104.08 ms | 566.7 ms |
| LuaJIT | 115.42 ms | 379.5 ms |
| Dart AOT | 140.23 ms | 280.0 ms |
| JS (Node) | 191.15 ms | 282.9 ms |
| ocaml | 199.15 ms | 306.3 ms |
| JS (Deno) | 220.92 ms | 291.5 ms |
| Java (JIT) | 259.00 ms | 537.8 ms |
| Numpy | 374.95 ms | 599.2 ms |
| JS (Bun) | 821.08 ms | 894.7 ms |
| Python | 1.69 s | 1.768 s |
| Lua | 2356.96 ms | 2.989 s |
| Language | Processing Time | Total (PT + I/O) |
|---|---|---|
| Rust Concurrent | 15.77 ms | 32.8 ms |
| Go Concurrent | 18.98 ms | 50.6 ms |
| Swift Concurrent | 39.95 ms | 434.0 ms |
| F# Concurrent | 40.47 ms | 857.4 ms |
Old Results with details (on my machine)
| Language | Processing Time | Total (+ I/O) | Details |
|---|---|---|---|
| Rust | - | 4.5s | Initial |
| Rust v2 | - | 2.60s | Replace std HashMap with fxHashMap by phazer99 |
| Rust v3 | - | 1.28s | Preallocate and reuse map and unstable sort by vdrmn and Darksonn |
| Rust v4 | - | 0.13s | Use Post index as key instead of Pointer and Binary Heap by RB5009 |
| Rust v5 | 38ms | 52ms | Rm hashing from loop and use vec[count] instead of map[index]count by RB5009 |
| Rust v6 | 23ms | 36ms | Optimized Binary Heap Ops by scottlamb |
| Rust Rayon | 9ms | 22ms | Parallelize by masmullin2000 |
| Rust Rayon | 8ms | 22ms | Remove comparison out of hot loop |
| ⠀ | ⠀ | ⠀ | ⠀ |
| Go | - | 1.5s | Initial |
| Go v2 | - | 80ms | Add rust optimizations |
| Go v3 | 56ms | 70ms | Use goccy/go-json |
| Go v3 | 34ms | 55ms | Use generic binaryheap by DrBlury |
| Go v4 | 26ms | 50ms | Replace binary heap with custom priority queue |
| Go v5 | 20ms | 43ms | Remove comparison out of hot loop |
| Go Con | 10ms | 33ms | Go concurrency by tirprox and DrBlury |
| Go Con v2 | 5ms | 29ms | Use arena, use waitgroup, rm binheap by DrBlury |
| ⠀ | ⠀ | ⠀ | ⠀ |
| Python | - | 7.81s | Initial |
| Python v2 | 1.35s | 1.53s | Add rust optimizations by dave-andersen |
| Numpy | 0.57s | 0.85s | Numpy implementation by Copper280z |
| ⠀ | ⠀ | ⠀ | ⠀ |
| Crystal | 50ms | 96ms | Inital w/ previous optimizations |
| Crystal v2 | 33ms | 72ms | Replace binary heap with custom priority queue |
| ⠀ | ⠀ | ⠀ | ⠀ |
| Odin | 110ms | 397ms | Ported from golang code |
| Odin v2 | 104ms | 404ms | Remove comparison out of hot loop |
| ⠀ | ⠀ | ⠀ | ⠀ |
| Dart VM | 125ms | 530ms | Ported frog golang code |
| Dart bin | 274ms | 360ms | Compiled executable |
| ⠀ | ⠀ | ⠀ | ⠀ |
| Vlang | 339ms | 560ms | Ported from golang code |
| ⠀ | ⠀ | ⠀ | ⠀ |
| Zig | 80ms | 110ms | Provided by akhildevelops |