# Some SIMD in your OCaml **URL:** \ **Category:** Community\ **Created:** [September 6, 2020, 2:20pm UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367 "2020-09-06T14:20:27Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![anmolsahoo25](https://avatars.discourse-cdn.com/v4/letter/a/b9bd4f/32.png) [@anmolsahoo25](https://discuss.ocaml.org/u/anmolsahoo25)\ **Post date:** [September 6, 2020, 2:20pm UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/1 "2020-09-06T14:20:27Z")
Fresh from a weekend of hacking, I would like to share some results of an experiment I conducted of creating a library for exposing Intel AVX2 intrinsics to OCaml code. AVX2 is an instruction set subset that adds data-parallel operations in hardware. I chose to fork the amazing [bigstringaf](https://github.com/inhabitedtype/bigstringaf) library and modified it. You can find the additions to the code here - [bigstringaf\_simd](https://github.com/anmolsahoo25/bigstringaf/blob/8df94c4fb5607317ee9634611784eea65368a270/lib/bigstringaf_simd.mli#L287). ### Overview Given a type `Bigstring.t` (1 dimensional byte arrays) there now exist functions such as - ```auto val cmpeq_i8 : (t * int) -> (t * int) -> (t * int) -> unit ``` So `cmpeq_i8 (x,o1) (y,o2) (z,03)` will compare 32 bytes starting at `o1` and `o2` from `x` and `y` respectively and store the result in `z` at `o3`. ### Why? This was mainly an exercise in curiosity. I just wanted to learn whether something like this is viable. I also want to see if adding some type-directed magic + ppx spells can let us write data parallel code much more naturally similar to what `lwt / async` did for async code. At the same time, you might ask - why not use something like Owl (which already has good support for data-parallel operations)? Apart from the fact that such libraries are oriented towards numerical code, I would also like to explore if we can operate directly on OCaml types and cast them into data parallel algorithms. Like how `simdjson` pushed the boundaries of JSON parsing, it would be nice to port idiomatic code to data-parallel versions in OCaml. Can we, at some point, have generic traversals of data-types, which are actually carried out in a data-parallel fashion? ### Does it work? Given the limitation of the current implementation (due to foreign function calls into C), I still found some preliminary results to be interesting! Implementing the `String.index` function, which returns the first occurence of a char, the runtime for finding an element at the `n-1` position in an array with `320000000` elements is - ```auto serial: 1.12 seconds simd: 0.72 seconds (1.5x) ``` I still have to do the analysis what the overhead of the function call into C is (even with `[@@noalloc]`! ### Future directions It would be interesting to see, if we can create a representation which encapsulates the various SIMD ISA’s such as AVX2, AVX512, NEON, SVE etc. Further more, it would be really interesting to see if we can use ppx to automatically widen `map` functions to operate on blocks of code, or automatically cast data types in a data parallel representation. ### Disclaimer This was mostly a hobby project, so I cannot promise completing any milestones or taking feature requests etc. I definitely do not recommend using this in production, because of the lack of testing etc. ---
**Author:** ![UnixJunkie](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/unixjunkie/32/638_2.png) [@UnixJunkie](https://discuss.ocaml.org/u/UnixJunkie)\ **Post date:** [September 8, 2020, 4:11am UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/2 "2020-09-08T04:11:05Z")
Quite interesting project. ---
**Author:** ![anmolsahoo25](https://avatars.discourse-cdn.com/v4/letter/a/b9bd4f/32.png) [@anmolsahoo25](https://discuss.ocaml.org/u/anmolsahoo25)\ **Post date:** [September 8, 2020, 1:04pm UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/3 "2020-09-08T13:04:00Z")
Thank you! Very early days, hopefully I can get it to a useful form soon! ---
**Author:** ![Kakadu](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/kakadu/32/1204_2.png) [@Kakadu](https://discuss.ocaml.org/u/Kakadu)\ **Post date:** [September 8, 2020, 2:26pm UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/4 "2020-09-08T14:26:23Z")
Do you have any kind of vision about which class of programs may benefit for fancy amd64 instructions? I mentioned autovectorization topic in a chatroom somewhere on ICFP2020. Folks from Janestreet said that it’s unlikely that they are writing code that could benefit from this kind of instructions. ---
**Author:** ![c-cube](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/c-cube/32/1727_2.png) [@c-cube](https://discuss.ocaml.org/u/c-cube)\ **Post date:** [September 8, 2020, 2:47pm UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/5 "2020-09-08T14:47:52Z")
Isn’t it supposed to be useful even for simple `memcpy` or string search? I don’t know if it’s the fancy newer instructions, but OCaml could certainly use faster `copy`/`blit`/`index` on `bytes`, too. ---
**Author:** ![anmolsahoo25](https://avatars.discourse-cdn.com/v4/letter/a/b9bd4f/32.png) [@anmolsahoo25](https://discuss.ocaml.org/u/anmolsahoo25)\ **Post date:** [September 8, 2020, 4:21pm UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/6 "2020-09-08T16:21:48Z")
@Kakadu Though their are quite a few fancy instruction set subsets in amd64, I think SIMD instruction sets like AVX / AVX2 / AVX512 are becoming more common now. If you look at DPDK, which does userspace network packet manipulation, simdjson which does JSON parsing and Hyperscan for regex matching, all of them benefit from SIMD. The problem I feel here is that SIMD has always been targeted towards math-heavy code, but I do feel there is some potential for defining generic maps / traversals etc over OCaml ADT’s that can benefit from SIMD. That would possibly open-up _any_ code benefiting from SIMD (but this is a pipe-dream!) At the same time, I think if you are optimizing for latency (which in my WILD GUESS, Jane Street is probably interested in), then i don’t think SIMD helps much there. Wherever throughput is a concern, SIMD would be more helpful. @c-cube For the case of copy / blit, I think it would be hard to beat the system `memcpy / memmove`. There is an example here [FastMemcpy](https://github.com/skywind3000/FastMemcpy), which uses AVX to beat `memcpy/memmove` but I don’t think the effort is worth (maybe?). At the same time, the index function is quite interesting, because by using a vectorized version which goes through a c call, I am able to get a 1.5x speedup. Would be interesting to see if the performance benefit if that instruction can be emitted inline. ---
**Author:** ![c-cube](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/c-cube/32/1727_2.png) [@c-cube](https://discuss.ocaml.org/u/c-cube)\ **Post date:** [September 8, 2020, 4:58pm UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/7 "2020-09-08T16:58:02Z")
Yes, even calling the C memcpy for `bytes` functions would often result in a performance improvement, imho. I’m not sure if the compiler maintainers are willing to add these instructions to the code generator, or any instruction that goes beyond x86\_64. (I’d love to have popcnt otherwise…) ---
**Author:** ![anmolsahoo25](https://avatars.discourse-cdn.com/v4/letter/a/b9bd4f/32.png) [@anmolsahoo25](https://discuss.ocaml.org/u/anmolsahoo25)\ **Post date:** [September 8, 2020, 5:04pm UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/8 "2020-09-08T17:04:37Z")
The `bigstringaf` library already implements blits / copies as memcpy / memmove! ---
**Author:** ![c-cube](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/c-cube/32/1727_2.png) [@c-cube](https://discuss.ocaml.org/u/c-cube)\ **Post date:** [September 8, 2020, 5:44pm UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/9 "2020-09-08T17:44:16Z")
Indeed, but `bytes` could also use some love! ---
**Author:** ![zozozo](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/zozozo/32/59_2.png) [@zozozo](https://discuss.ocaml.org/u/zozozo)\ **Post date:** [September 8, 2020, 6:04pm UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/10 "2020-09-08T18:04:02Z")
I’m a bit puzzled by your comment here. As far as I can tell, `Bytes.blit` actually calls `memmove` currently, cf [https://github.com/ocaml/ocaml/blob/trunk/stdlib/bytes.ml#L36](https://github.com/ocaml/ocaml/blob/trunk/stdlib/bytes.ml#L36) and [https://github.com/ocaml/ocaml/blob/trunk/runtime/str.c#L363](https://github.com/ocaml/ocaml/blob/trunk/runtime/str.c#L363) (the reason for using `memmove` and not `memcpy` is to correctly handle overlapping source and destinations iirc). ---
**Author:** ![c-cube](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/c-cube/32/1727_2.png) [@c-cube](https://discuss.ocaml.org/u/c-cube)\ **Post date:** [September 8, 2020, 6:21pm UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/11 "2020-09-08T18:21:20Z")
> I’m a bit puzzled by your comment here. As far as I can tell, `Bytes.blit` actually calls `memmove` currently, cf [ocaml/stdlib/bytes.ml at trunk · ocaml/ocaml · GitHub](https://github.com/ocaml/ocaml/blob/trunk/stdlib/bytes.ml#L36) and [ocaml/runtime/str.c at trunk · ocaml/ocaml · GitHub](https://github.com/ocaml/ocaml/blob/trunk/runtime/str.c#L363) (the reason for using `memmove` and not `memcpy` is to correctly handle overlapping source and destinations iirc). I stand corrected 🙂 In practice memmove and memcpy are the same at least in glibc, as far as I know. It’s good to know! My point still stands for `index`, but it’s weaker now. ---
**Author:** ![bluddy](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bluddy/32/104_2.png) [@bluddy](https://discuss.ocaml.org/u/bluddy)\ **Post date:** [September 8, 2020, 6:28pm UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/12 "2020-09-08T18:28:06Z")
I think the reality is that outside of numeric computation, it’s pretty tough to use SIMD in a functional language. Functional languages just don’t match up with SIMD data patterns, which are array-based. A blob of string data is not a useful data type for OCaml – it immediately needs to be transformed to a more convenient data structure. On the other hand, a blob of numeric data is often well structured with predefined data lengths, and so can be carried around or transformed with computation occurring as `map` iterations over the data, which is what `Owl` does. ---
**Author:** ![UnixJunkie](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/unixjunkie/32/638_2.png) [@UnixJunkie](https://discuss.ocaml.org/u/UnixJunkie)\ **Post date:** [September 9, 2020, 1:07am UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/13 "2020-09-09T01:07:28Z")
I could imagine a specific array library, or even the Bigarray library (or a specific version of it), exposing some functions to exploit SIMD instructions. This being said, I’m going to test this to see if GPUs are of any use to me: [https://futhark-lang.org/](https://futhark-lang.org/) ---
**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\ **Post date:** [September 9, 2020, 7:43am UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/14 "2020-09-09T07:43:26Z")
> [@c-cube](#): > > In practice memmove and memcpy are the same at least in glibc, as far as I know. This is no longer true since 2010. (At the time, this caused some severe bugs all over the place, when people suddenly discovered they could no longer incorrectly use `memcpy` to perform overlapping moves.) More precisely, here is the definition of `memmove`. This looks identical to `memcpy`, except that the macro `USE_AS_MEMMOVE` is set, which adds some checks for overlapping. (And this macro is unset for `memcpy`). ```auto #define USE_AS_MEMMOVE #define MEMCPY __memmove_ssse3 #define MEMCPY_CHK __memmove_chk_ssse3 #include "memcpy-ssse3.S" ``` ---
**Author:** ![perry](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/perry/32/518_2.png) [@perry](https://discuss.ocaml.org/u/perry)\ **Post date:** [September 13, 2020, 1:17pm UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/15 "2020-09-13T13:17:31Z")
Modern C and C++ compilers (like gcc and llvm) make heavy use of SIMD instructions on architectures that provide them because they produce serious speedups. Perhaps the OCaml compiler could do the same. ---
**Author:** ![jfeser](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/jfeser/32/2093_2.png) [@jfeser](https://discuss.ocaml.org/u/jfeser)\ **Post date:** [September 13, 2020, 5:40pm UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/16 "2020-09-13T17:40:10Z")
> [@bluddy](#): > > Functional languages just don’t match up with SIMD data patterns, which are array-based. I don’t think this is necessarily true. There’s this neat paper from a few years ago that extended a stream type with simd support and got a ~2x performance improvement. The interface is still nicely functional; all the simd details are hidden. [https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/haskell-beats-C.pdf](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/haskell-beats-C.pdf) ---
**Author:** ![anmolsahoo25](https://avatars.discourse-cdn.com/v4/letter/a/b9bd4f/32.png) [@anmolsahoo25](https://discuss.ocaml.org/u/anmolsahoo25)\ **Post date:** [September 13, 2020, 6:01pm UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/17 "2020-09-13T18:01:39Z")
Agreed @jfeser, I don’t see any reason why FP patterns cannot be mapped to SIMD programming. At the end of the day everything can be hidden as an abstract datatype! 😛 Thanks for the paper suggestion! @perry, not a big fan of compilers rolling SIMD / vector compilers. Too much complexity to effectively manage and it is definitely not a common enough application to warrant support for everyone. A library approach to SIMD is much more tenable, in my opinion. ---
**Author:** ![perry](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/perry/32/518_2.png) [@perry](https://discuss.ocaml.org/u/perry)\ **Post date:** [September 13, 2020, 6:38pm UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/18 "2020-09-13T18:38:54Z")
> [@anmolsahoo25](#): > > not a big fan of compilers rolling SIMD / vector compilers. Too much complexity to effectively manage and it is definitely not a common enough application to warrant support for everyone. All modern processors do SIMD, and somehow, people using languages like C++ manage to write compilers that handle the complexity. The result is that they get enormous performance wins because single thread performance has stalled out on modern processors and explicit parallelism is how people now get speed increases. If you play with the output of compilers like gcc and clang/LLVM, you will see that vector instructions are inserted into pretty much every sort of program imaginable. This is because it substantially improves performance, even in everyday code. You cannot get this sort of benefit from using SIMD instructions in libraries in very limited contexts. ---
**Author:** ![bluddy](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bluddy/32/104_2.png) [@bluddy](https://discuss.ocaml.org/u/bluddy)\ **Post date:** [September 13, 2020, 7:57pm UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/19 "2020-09-13T19:57:39Z")
This is the exception that proves the rule IMO. Note the data type they use: Vector. At some point, data has to occupy adjacent memory cells to be viable for SIMD operations. This is not typical of FP data structures at all. In a language with monitored side effects (such as Haskell), stream fusion allows several map/fold operations to be strung together, much like we do for the Iter or Seq type in OCaml. You can then unroll a few of these loops to use up the SIMD registers. But notice that this isn’t very different from simply using tensor data types, and manipulating them with operations that adjust the whole tensor. In both cases, the main target is numerical data, and in both cases, you end up manipulating batches of data. In fact, I would suggest that the latter representation is generally superior in this case, since the user is aware that he is manipulating batches of data and therefore thinking at a higher conceptual level. This paper happens to have been written before the explosion of `numpy` (and its eventual arrival to OCaml in the form of `owl`), and therefore still discusses at the level of manipulating individual numbers, when the world has moved on to thinking about large groups of numbers and their manipulation (for machine learning and other mathematical applications). Again, note that this is a very specific niche – purely numeric data, organized together in large, regular batches. ---
**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\ **Post date:** [September 14, 2020, 6:01am UTC](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367/20 "2020-09-14T06:01:24Z")
> [@bluddy](#): > > At some point, data has to occupy adjacent memory cells to be viable for SIMD operations. Nowadays, instruction sets provide gather-load and scatter-store instructions, so they no longer require adjacent memory cells (since 2013 for x86, since 2016 for ARM). Theoretically, gather-scatter instructions are meant to load/store disjoint elements from a single array. But nobody prevents you from having the array start at address zero and cover the whole address space, so that the indices are actual memory addresses. But to be honest, compilers are just bad at recognizing gather-scatter operations when vectorizing, so one has to manually write such accesses using intrinsics in practice. [Next page](https://discuss.ocaml.org/t/some-simd-in-your-ocaml/6367.md?page=2)