submissions perf

[samir-]

i highly suspect that submissions are not run in the same conditions.
specifically mmap submissions benefit from RAM cache and this highly affects speed on successive runs and also runs of contestant executing after another using mmap too. can you double-check if this is the case for the top solutions?

Theoretically a SSD disk (the best) speed is at most 500Mb/s, given this,a lower bound for any solution shouldn't be less than the 40s either using mmap or classic io file descriptor read.

To reproduce:
to drop cache: sudo sh -c "sync; echo 3 > /proc/sys/vm/drop_caches"
OR to just test again some top solutions, I think you will have big diffs when run in some order.

Suggestions:

• either run the consecutive runs after doing a drop cache so that each submission is not affecting the next one. (the disk/mem cache will come into play but per user)
• purge cache at each run (which is not ideal as you are exposed to hardware variance and any optimization on processing is no longer meaningful against the io noise)
  WDYT ?
  @aboullaite @chermehdi

[aboullaite]

Thanks for flagging. Just to let you know that we're discussing this but i am slightly overwhelmed 😅 expect some delay

[chermehdi]

Hello @samir- ,

Thanks for flagging this, we are aware of the potential number skew, but since most we run the solutions multiple times, we expect that everyone would benefit from having the warm cache (to make server load to a minimal without skewing the results). but rest assured, before releasing the final results/numbers all the solutions will go through a full clean run and the we will remove any outliers in the times that we got.

The approach was a compromise between having something that gives rough numbers and not having to wait ages for a verdict as we get more submissions, but more thought will be put into deciding who is the winner. (dropping the cache is something that we planned to do in the final run once the submissions are closed).

[samir-]

full clean run and the we will remove any outliers in the times that we got

you mean running each solution X time successively (including the warm cache) and taking the average time of the rough converged time. like in this example (1m, 10s, 10s , 9s, 9.5s) you will take average on the last 4 ?
It's interesting to know if cache would be warm organically so that we can focus on IO (that is very noisy given the network disk and so on ) or processing itself (which is more controllable and reproducible in the long run).
Thanks @chermehdi

[chermehdi]

This is roughly what I am thinking about

1. drop the cache from previous runs
2. run the solution 10 times (instead of the original 5)
3. remove the outliers (slowest - fastest)
4. AVG the remaining 8

This is by no means sufficient for an accurate measurement, but I believe it's fair (since everyone would go though the same process and running more times would help smooth out any rough edges).

[samir-]

yes agree. that a good base. it benefits the processing time optimizations instead of IO noise.

[pcordes]

Median is usually a good metric for performance since it automatically ignores slow outliers, especially on a system that's not perfectly idle so other load can slow down some runs.
Fast outliers are usually rare, but if they happen they're usually real unless there's something wrong with the timing method. Or if you're timing on a machine that really isn't idle most of the time, but occasionally there are dips in whatever is competing for shared resources like memory bandwidth or I/O.

---

I wouldn't suggest dropping caches; if the machine has enough RAM to keep the test file hot in memory, you want it to stay there. It will benefit both mmap and read, although mmap is the fastest way to read a through file that's hot in the pagecache, on OSes like Linux with good fault-ahead / fault-around to wire up pages into the HW page tables so you'll just get a TLB miss (or successful TLB prefetch) for most pages instead of a soft page fault. (Like maybe one actual soft page fault per 8 or 16 pages you touch.)

IIRC, read can sometimes be better for files that aren't, but it has to do a memcpy inside the kernel to the user's buffer (e.g. Linux's copy_to_user kernel function.)

@samir- the fastest SATA SSDs have sequential-read performance somewhere below 600 MB/s, e.g. https://www.tomshardware.com/reviews/best-ssds,3891.html mentions Crucial's MX500 reading at 560 MB/s. With transparent compression (e.g. BTRFS using zstd or lz4), the actual data rate for reading this text file could be higher depending on how compressible it is, like maybe a factor of 2.

But SATA is obsolete for SSDs. NVMe uses PCI-express directly. Sequential read speeds for new SSDs worth buying in 2024 range from 3500 MB/s to 7000 MB/s. (Or the fastest consumer-grade PCIe 5.0 SSD currently, Crucial T700, reads at 12400 MB/s. That's half of DRAM bandwidth on a desktop from a few years ago.)
NVMe SSDs from several years ago are slower, e.g. my 256 GB Intel 600p SSD only reads about 715 MB/s but still faster than 500 MB/s.

Anyway, making I/O more expensive and a potential bottleneck doesn't seem like a good idea for comparing efficient text-parsing and data-structure usage.