6 ms·
There are some good ideas for this type of problem here: https://github.com/dannyvankooten/1brc https://github.com/dannyvankooten/1brc After you deal with pars
by pama 3y ago
There are some good ideas for this type of problem here: https://github.com/dannyvankooten/1brc https://github.com/dannyvankooten/1brc
After you deal with parsing and hashes, basically you are IO limited, so mmap helps. The C code takes less than 1.4s without any CUDA access. Because there is no compute to speak of, other than parsing and a hashmap, a reasonable guess is that even for the optimal CUDA implementation, the starting of kernels and transfer of data to the GPU would likely add a noticeable bottleneck and make the optimal CUDA code slower than this pure C code.
- _zoltan_ 3y agothis is true for small datasets. on large datasets, once loaded into GPU memory, cross GPU shuffling with NVLink is going to be much faster than CPU to RAM. on the H100 boxes with 8x400Gbps, IO with GDS is also pretty fast. for truly IObound tasks I think a lot of GPUs beats almost anything :-)
- 15155 3y agoTry an array of FPGAs.
- _zoltan_ 3y agoI've never been a fan plus good luck getting 800GB/s across.
- dan-robertson 3y agoWhy does that help with IO bandwidth?
- 15155 3y agoBecause every transceiver pair can do 32Gb/s or 56Gb/s and you have dozens of them.
- candido_heavyai 3y agoI am testing a gh200 and the speed you can access the system memory is amazing.. Assuming you have already encoded the station into a smallint and the size of the dataset would be around 6gb that on such system takes just 20 ms to be transfered (I am sure about that because I'm observing transfer a 9.5gb that took about 33ms right now).
- konstantinua00 3y ago1 billion rows is "small dataset"?
- _zoltan_ 3y agoeh, it's just two columns. 12 or 13GB IIRC.
- PeterisP 3y agoThe meaningful boundary between small data and large data is the difference whether the whole dataset/processing is expected to fit in the RAM of a single common machine. From that perspective, 1 billion rows a borderline case, which can be small or large depending on how large the rows are - and in this particular challenge the rows are tiny.
- belter 3y agoJust the click stream data of four 15 year old's, chilling out on the living room while watching TikTok videos....
- pama 3y agoYes, GDS will accelerate the IO to the GPU. I’d love to see the above C code compared to hyperoptimized GPU code on the right hardware, but I don’t want to accidentally nerd snipe myself :-) The unfortunate part of this particular benchmark is that once you have the data in the right place in your hardware there is very little compute left. The GPU code would probably have constant performance with an additional couple thousand operations on each row whereas CPU would slow down. https://docs.nvidia.com/gpudirect-storage/overview-guide/index.html https://docs.nvidia.com/gpudirect-storage/overview-guide/ind...
- _zoltan_ 3y agoso you'd rather nerd snipe others, gotcha ;) :D
- pama 3y agoHaha. Apologies. I hope I didn’t accidentally make anyone waste their time. If they did I’m sure there are people interested in hiring such people anyways so maybe it’s a time invested well in the end.
- pama 3y agoThis would be the code to beat. Ideally with only 8 cores but any number of cores is also very interesting. https://github.com/gunnarmorling/1brc/discussions/710 https://github.com/gunnarmorling/1brc/discussions/710
- nwallin 3y ago> on large datasets, once loaded into GPU memory, You're yada-yada-yadaing the best part. If the disk can process the data at 1GB/s, the CPU can process the data at 2GB/s, the GPU can process the data at 32GB/s, then the CPU can process the data at 1GB/s and the GPU can process the data at 1GB/s. (also, personally, "large dataset" is a short way to say "doesn't fit in memory". if it fits in memory it's small, if it doesn't fit in memory it's large. but that's just my opinion. I generally avoid calling something a "large" or "small" dataset because it's an overloaded term that means different things to different people.)
- ww520 3y agoActually on modern systems it’s pure compute plus memory bounded. For this problem hashmap lookup is the biggest bottleneck. Parsing takes time away as well but not as bad as hashmap.
- petermcneeley 3y agoFrom what I can tell the number of unique elements is pretty small. This would mean the hash map will sit in cache. Parsing is likely the bottleneck; I dont see any use of SIMD in the linked code.
- ww520 3y agoThe key can be up to 100 bytes. The key in the hashmap is in cache. The key being compared is from main memory. Basically the whole file in memory is being gone through and compared. With 1 billion rows it’s about 16GB data in memory for a 16-byte average row. That’s approaching the memory bandwidth limit for a second, making it a memory bound problem.
- petermcneeley 3y agoThis really depends on number of unique keys. If they sit in L1-L2: the bandwidth of these caches is an order of magnitude greater than main memory. This problem is quite a Nerd Snipe so it a good thing that I dont have a computer with more than 16 GB or I might end up trying it myself.
- emcq 3y agoThe 1.4s is _after_ having the file loaded into RAM by the kernel. Because this is mostly I/O bound, it's not a fair comparison to skip the read time. If you were running on a M3 mac you'd might get less than 100ms if the dataset was stored in RAM. If you account for time loading from disk, the C implementation would be more like ~5s as reported in the blog post [1]. Speculating that their laptop's SSD may be in the 3GB/s range, perhaps there is another second or so of optimization left there (which would roughly work out to the 1.4s in-memory time). Because you have a lot of variable width row reads this will be more difficult on a GPU than CPU. [1] https://www.dannyvankooten.com/blog/2024/1brc/ https://www.dannyvankooten.com/blog/2024/1brc/
- ww520 3y agoAlso this uses 16 threads while the contest restricts to running in 8 cores. Needs to compare the benchmarks in the same environment to make a fair comparison.
- pama 3y agoThe AMD Ryzen 4800U has 8 cores total so the author follows the contest restriction. This CPU supports hyperthreading. (I’d be very interested in seeing hyperoptimized CUDA code using unlimited GPU cores FWIW.)
- ww520 3y agoGood to know. I didn’t know the contest has no limit on hyperthread.
- fulafel 3y ago1brc in the contest had SMT disabled [0]. (hyperthreading is an intel marketing name and trademark for their implementation of smt, but the benchmark was run on an amd cpu) [0] https://github.com/gunnarmorling/1brc/issues/189#issuecomment-1889394343 https://github.com/gunnarmorling/1brc/issues/189#issuecommen...