4 ms·

How's Nim faring with regards to easy programming for multicores? (I think that's the main selling point of Go).

cb321 5y ago
First, I like that you said "multicores" and not "multithreads". Default-sharing of all memory is overrated. Sometimes it is useful/necessary, but people reach for threads too readily, IMO. For multiprocessing (like Python's module of that name), you can roll your own little system in probably 100 lines of code or use something like this [1] with an example program [2]. For me, that toy program runs 1.5-2x faster than ripgrep on the same (admittedly limited) problem on Linux. { I suspect this perf diff is due to mmap IO being faster than syscall IO due to SIMD register use as discussed here [3], but this deserves deeper investigation than I have time for right now. If my hunch is right, that may constitute further argumentative support for not leaping to threads even if the programming language "makes them 'easy'", though. } As for threads/parallelism with shared memory in Nim..Honestly, there is probably too much to recap. Weave [4] would be a good place to start reading, though, or searching the Nim Forum. [1] https://github.com/c-blake/cligen/blob/master/cligen/procpool.nim [2] https://github.com/c-blake/cligen/blob/master/examples/grl.nim [3] https://news.ycombinator.com/item?id=24842648 [4] https://github.com/mratsim/weave
- burntsushi 5y ago
  Is it possible to share the commands/inputs you used to run a benchmark with your code against ripgrep? (Including commands to compile your Nim program.)
  - cb321 5y ago
    This has some Zsh-isms but should get you going, assuming it is even reproducible across machines. $ cd cligen-github-root/examples # default system nim.cfg $ nim c -d:danger --gc:arc -d:useMalloc --passC:-flto --passL:-flto grl # best to fetch this while you can as they get updated regularly # oh yeah, just unpacked; not configured/anything. $ cd /dev/shm/linux-5.12.5 # Zsh-ism to eliminate file tree traversal variation $ fs=(**.[ch]) # On an Intel i7-6700K $ repeat 5 utime ~1/grl -sburntsushi $fs 0.143836198 0.23 0.21 305.9% 0.137177744 0.22 0.22 320.8% 0.136714417 0.22 0.22 321.8% 0.149867097 0.23 0.22 300.3% 0.139042282 0.22 0.22 316.5% # make sure there is no ripgreprc file. $ repeat 5 utime rg burntsushi $fs 0.204383740 0.33 0.26 288.7% 0.200495993 0.34 0.25 294.3% 0.205767854 0.37 0.22 286.7% 0.200485116 0.33 0.25 289.3% 0.201692769 0.34 0.24 287.6% $ rg --version ripgrep 12.1.1 -SIMD -AVX (compiled) +SIMD +AVX (runtime) 200.5/136.7 =~ 1.47x OS for the above is Linux 5.12 running on bare metal. When I do a gcc PGO build I can squeeze about another 7 ms off that 136.7 time, but this is probably not very informative. Honestly, even 1.5x is kinda small, too. Anyway, were I to study this in more detail, as it sounds like you may be wanting to do, my recommendation would be to just factor out the substring/regex search (rg's vs glibc memmem, etc.) and study a more "pure IO" case. E.g., just switch to memchr(non-existent char) or such (e.g. Daniel Lemire's Faster 64-bit universal hashing using carry-less multiplications, Journal of Cryptographic Engineering is very fast or maybe even a SIMD-summation) to force all the IO but do other things SIMD-efficiently/at the highest GB/sec easily achievable. Then try that same simplified program with ripgrep's file size heuristics with threads vs the grl N-kid processes + always mmap. Just fewer moving parts/better isolation of behaviors. This also might lead to more general/re-applicable knowledge for the best way to do read-only multi-core file IO, not only tuning ripgrep or only Rust or only any PL. If it all holds up, and that same "test setup" could be applied to differing OS contexts like OSX/Win/etc. and then maybe it might be worthwhile re-jiggering ripgrep IO. (It is not a foregone conclusion the answer will be the same across OSes or CPUs, or even that my hunches/hypotheses are correct. I am trying to help here without making strong, general claims to be cross-examined upon, as is the Internet's way...)
    - burntsushi 5y ago
      Thanks! Appreciate it. For clarity, this is the corpus I downloaded: https://cdn.kernel.org/pub/linux/kernel/v5.x/linux-5.12.5.tar.xz https://cdn.kernel.org/pub/linux/kernel/v5.x/linux-5.12.5.ta... And I used fs=(**/*.h) since including the C files caused the argument list to be too long on my system. My CPU is a bit dated, but is a i7-6900K @ 3.2 GHz. My Nim version: $ nim --version Nim Compiler Version 1.4.6 [Linux: amd64] Compiled at 2021-04-26 Copyright (c) 2006-2020 by Andreas Rumpf active boot switches: -d:release -d:nativeStackTrace With those caveats, this is what I get on my system: $ TIMEFMT=$'%*E' $ repeat 5 time ~/clones/cligen/examples/grl -sburntsushi $fs 0.093 0.079 0.083 0.083 0.082 $ repeat 5 time rg --no-config burntsushi $fs 0.088 0.088 0.086 0.082 0.083 We can somewhat control for substring search by using 'zzzzzzzz'. It won't control for everything, but it should be close I think. $ repeat 5 time ~/clones/cligen/examples/grl -szzzzzzzz $fs 0.086 0.073 0.080 0.078 0.075 $ repeat 5 time rg --no-config zzzzzzzz $fs 0.085 0.087 0.084 0.084 0.086 If I run with jobs=1 for both tools, I get: $ repeat 5 time ~/clones/cligen/examples/grl -j1 -szzzzzzzz $fs 0.204 0.201 0.188 0.214 0.190 $ repeat 5 time rg --no-config -j1 zzzzzzzz $fs 0.261 0.239 0.231 0.226 0.256 Here's where it gets interesting. If I force ripgrep to use memory maps, then I get (first with parallelism, and then without): $ repeat 5 time rg --no-config --mmap zzzzzzzz $fs 0.399 0.328 0.354 0.343 0.357 $ repeat 5 time rg --no-config --mmap -j1 zzzzzzzz $fs 0.312 0.278 0.280 0.266 0.245 I think on the one hand, I'm confused as to why I can't reproduce your result. But the more interesting thing to me is why ripgrep is so slow when it uses memory maps, but your program is not. The strace output for ripgrep also shows more syscalls than I would expect, so I'll be investigating that as well. There are also lots of 'pselect6' syscalls in your program. Do you know what those are from? Anyway, thanks for the interesting benchmark! Some interesting bits to investigate!
      - cb321 5y ago
        Sorry. In my kernel build script I patch _STK_LIM in include/uapi/linux/resource.h and MAX_ARG_PAGES in include/linux/binfmts.h to boost my command line lengths. There was a short time when Rob Pike had some patch that fixed this with a fun comment like "dynamic memory allocation is a done deal, guys". It could be that .h files are smaller than .c files (or just fewer/less total data) making it harder to reproduce. Another element to add to my suggested research program above besides eliminating string search algos would be to standardize file sizes to all 100 KiB or something. Generate them with random data or some such. Play around with file sizes in your experiments, etc. Besides that, your CPU has twice the cores as mine and we may have pretty different memory bandwidths as mine has very low latency and high BW RAM. Reproduction is actually not generally very easy which is why I said 1.5x was not so big. I often find it hard to reproduce ratios <2..3x, but it does look like a number of cases of the min of 5 `grl` beating `ripgrep` in your tests. Anyway, this is all really just the start of some project, not the end. `grl` is really just a demo program for the 8-bit clean message passing variant in `procpool` (similar to Python's multiprocessing module). `procpool` uses parent-kid pipes for its communication. The pselect6's come from using select on those N pipes. And, yeah, a lot of selects are expected since the filename passing-answer receiving happens a lot with a lot of files. { Yes, yes...I know past 1024 fd's select will be a problem, but TSMC only just hit that 1nm mark. So, we probably still have a few years before I personally can access 1024 core-thread machines.. ;-) ;-) } mmaps and threads was discussed already in [3] linked in my first post of this thread with a brief summary. To recap briefly - since threads share all memory and since mmap alters those page tables, it is plausible the kernel just locks the whole process out of simplicity, blocking execution of other threads. It is also possible OS-? can use devious tricks/semantics to avoid that locking, but I am unaware of an exhaustive survey or proof of impossibility. Because in `procpool`/`grl` the kids which are what do the per-file mmaps, are their own processes there is no suspension of the other kids when they mmap. So, they can realize the faster IO (from SIMD register use, done by Linux for context switch optimization or "performance in the large/system-wide"). This is (perhaps) why your last test has better performance without any parallelism. I had meant to test this last time we discussed mmap & threads, but didn't at the time. `grl` is just a very preliminary test along those lines. This is all at least partly theoretical. Someone ought to study it and write a nice blog article about it. I do not have that kind of time right now (or a blog). Or, for all I know, nice academic paper(s) already study this somewhere. I have not looked. Sadly, as old as this thread is, the general HN pool will probably not see any of this to crowd source such wisdom with direct pointers for you. I almost missed your question in my old threads checking, and I have kind of used up my time budget for this right now. You can email if you want. I get better notifies that way.
skynet-9000 5y ago
and channels... extremely useful for network servers.

First, I like that you said "multicores" and not "multithreads". Default-sharing of all memory is overrated. Sometimes it is useful/necessary, but people reach for threads too readily, IMO. For multiprocessing (like Python's module of that name), you can roll your own little system in probably 100 lines of code or use something like this [1] with an example program [2]. For me, that toy program runs 1.5-2x faster than ripgrep on the same (admittedly limited) problem on Linux. { I suspect this perf diff is due to mmap IO being faster than syscall IO due to SIMD register use as discussed here [3], but this deserves deeper investigation than I have time for right now. If my hunch is right, that may constitute further argumentative support for not leaping to threads even if the programming language "makes them 'easy'", though. } As for threads/parallelism with shared memory in Nim..Honestly, there is probably too much to recap. Weave [4] would be a good place to start reading, though, or searching the Nim Forum. [1] https://github.com/c-blake/cligen/blob/master/cligen/procpool.nim [2] https://github.com/c-blake/cligen/blob/master/examples/grl.nim [3] https://news.ycombinator.com/item?id=24842648 [4] https://github.com/mratsim/weave

burntsushi 5y ago
Is it possible to share the commands/inputs you used to run a benchmark with your code against ripgrep? (Including commands to compile your Nim program.)
- cb321 5y ago
  This has some Zsh-isms but should get you going, assuming it is even reproducible across machines. $ cd cligen-github-root/examples # default system nim.cfg $ nim c -d:danger --gc:arc -d:useMalloc --passC:-flto --passL:-flto grl # best to fetch this while you can as they get updated regularly # oh yeah, just unpacked; not configured/anything. $ cd /dev/shm/linux-5.12.5 # Zsh-ism to eliminate file tree traversal variation $ fs=(**.[ch]) # On an Intel i7-6700K $ repeat 5 utime ~1/grl -sburntsushi $fs 0.143836198 0.23 0.21 305.9% 0.137177744 0.22 0.22 320.8% 0.136714417 0.22 0.22 321.8% 0.149867097 0.23 0.22 300.3% 0.139042282 0.22 0.22 316.5% # make sure there is no ripgreprc file. $ repeat 5 utime rg burntsushi $fs 0.204383740 0.33 0.26 288.7% 0.200495993 0.34 0.25 294.3% 0.205767854 0.37 0.22 286.7% 0.200485116 0.33 0.25 289.3% 0.201692769 0.34 0.24 287.6% $ rg --version ripgrep 12.1.1 -SIMD -AVX (compiled) +SIMD +AVX (runtime) 200.5/136.7 =~ 1.47x OS for the above is Linux 5.12 running on bare metal. When I do a gcc PGO build I can squeeze about another 7 ms off that 136.7 time, but this is probably not very informative. Honestly, even 1.5x is kinda small, too. Anyway, were I to study this in more detail, as it sounds like you may be wanting to do, my recommendation would be to just factor out the substring/regex search (rg's vs glibc memmem, etc.) and study a more "pure IO" case. E.g., just switch to memchr(non-existent char) or such (e.g. Daniel Lemire's Faster 64-bit universal hashing using carry-less multiplications, Journal of Cryptographic Engineering is very fast or maybe even a SIMD-summation) to force all the IO but do other things SIMD-efficiently/at the highest GB/sec easily achievable. Then try that same simplified program with ripgrep's file size heuristics with threads vs the grl N-kid processes + always mmap. Just fewer moving parts/better isolation of behaviors. This also might lead to more general/re-applicable knowledge for the best way to do read-only multi-core file IO, not only tuning ripgrep or only Rust or only any PL. If it all holds up, and that same "test setup" could be applied to differing OS contexts like OSX/Win/etc. and then maybe it might be worthwhile re-jiggering ripgrep IO. (It is not a foregone conclusion the answer will be the same across OSes or CPUs, or even that my hunches/hypotheses are correct. I am trying to help here without making strong, general claims to be cross-examined upon, as is the Internet's way...)
  - burntsushi 5y ago
    Thanks! Appreciate it. For clarity, this is the corpus I downloaded: https://cdn.kernel.org/pub/linux/kernel/v5.x/linux-5.12.5.tar.xz https://cdn.kernel.org/pub/linux/kernel/v5.x/linux-5.12.5.ta... And I used fs=(**/*.h) since including the C files caused the argument list to be too long on my system. My CPU is a bit dated, but is a i7-6900K @ 3.2 GHz. My Nim version: $ nim --version Nim Compiler Version 1.4.6 [Linux: amd64] Compiled at 2021-04-26 Copyright (c) 2006-2020 by Andreas Rumpf active boot switches: -d:release -d:nativeStackTrace With those caveats, this is what I get on my system: $ TIMEFMT=$'%*E' $ repeat 5 time ~/clones/cligen/examples/grl -sburntsushi $fs 0.093 0.079 0.083 0.083 0.082 $ repeat 5 time rg --no-config burntsushi $fs 0.088 0.088 0.086 0.082 0.083 We can somewhat control for substring search by using 'zzzzzzzz'. It won't control for everything, but it should be close I think. $ repeat 5 time ~/clones/cligen/examples/grl -szzzzzzzz $fs 0.086 0.073 0.080 0.078 0.075 $ repeat 5 time rg --no-config zzzzzzzz $fs 0.085 0.087 0.084 0.084 0.086 If I run with jobs=1 for both tools, I get: $ repeat 5 time ~/clones/cligen/examples/grl -j1 -szzzzzzzz $fs 0.204 0.201 0.188 0.214 0.190 $ repeat 5 time rg --no-config -j1 zzzzzzzz $fs 0.261 0.239 0.231 0.226 0.256 Here's where it gets interesting. If I force ripgrep to use memory maps, then I get (first with parallelism, and then without): $ repeat 5 time rg --no-config --mmap zzzzzzzz $fs 0.399 0.328 0.354 0.343 0.357 $ repeat 5 time rg --no-config --mmap -j1 zzzzzzzz $fs 0.312 0.278 0.280 0.266 0.245 I think on the one hand, I'm confused as to why I can't reproduce your result. But the more interesting thing to me is why ripgrep is so slow when it uses memory maps, but your program is not. The strace output for ripgrep also shows more syscalls than I would expect, so I'll be investigating that as well. There are also lots of 'pselect6' syscalls in your program. Do you know what those are from? Anyway, thanks for the interesting benchmark! Some interesting bits to investigate!
    - cb321 5y ago
      Sorry. In my kernel build script I patch _STK_LIM in include/uapi/linux/resource.h and MAX_ARG_PAGES in include/linux/binfmts.h to boost my command line lengths. There was a short time when Rob Pike had some patch that fixed this with a fun comment like "dynamic memory allocation is a done deal, guys". It could be that .h files are smaller than .c files (or just fewer/less total data) making it harder to reproduce. Another element to add to my suggested research program above besides eliminating string search algos would be to standardize file sizes to all 100 KiB or something. Generate them with random data or some such. Play around with file sizes in your experiments, etc. Besides that, your CPU has twice the cores as mine and we may have pretty different memory bandwidths as mine has very low latency and high BW RAM. Reproduction is actually not generally very easy which is why I said 1.5x was not so big. I often find it hard to reproduce ratios <2..3x, but it does look like a number of cases of the min of 5 `grl` beating `ripgrep` in your tests. Anyway, this is all really just the start of some project, not the end. `grl` is really just a demo program for the 8-bit clean message passing variant in `procpool` (similar to Python's multiprocessing module). `procpool` uses parent-kid pipes for its communication. The pselect6's come from using select on those N pipes. And, yeah, a lot of selects are expected since the filename passing-answer receiving happens a lot with a lot of files. { Yes, yes...I know past 1024 fd's select will be a problem, but TSMC only just hit that 1nm mark. So, we probably still have a few years before I personally can access 1024 core-thread machines.. ;-) ;-) } mmaps and threads was discussed already in [3] linked in my first post of this thread with a brief summary. To recap briefly - since threads share all memory and since mmap alters those page tables, it is plausible the kernel just locks the whole process out of simplicity, blocking execution of other threads. It is also possible OS-? can use devious tricks/semantics to avoid that locking, but I am unaware of an exhaustive survey or proof of impossibility. Because in `procpool`/`grl` the kids which are what do the per-file mmaps, are their own processes there is no suspension of the other kids when they mmap. So, they can realize the faster IO (from SIMD register use, done by Linux for context switch optimization or "performance in the large/system-wide"). This is (perhaps) why your last test has better performance without any parallelism. I had meant to test this last time we discussed mmap & threads, but didn't at the time. `grl` is just a very preliminary test along those lines. This is all at least partly theoretical. Someone ought to study it and write a nice blog article about it. I do not have that kind of time right now (or a blog). Or, for all I know, nice academic paper(s) already study this somewhere. I have not looked. Sadly, as old as this thread is, the general HN pool will probably not see any of this to crowd source such wisdom with direct pointers for you. I almost missed your question in my old threads checking, and I have kind of used up my time budget for this right now. You can email if you want. I get better notifies that way.

skynet-9000 5y ago

and channels... extremely useful for network servers.