# Optimizing small vector operations **URL:** \ **Category:** Learning\ **Created:** [January 25, 2021, 1:45pm UTC](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160 "2021-01-25T13:45:33Z")\ **Posts on this page:** 16\ **Page:** 2
**Author:** ![n4323](https://avatars.discourse-cdn.com/v4/letter/n/97f17d/32.png) [@n4323](https://discuss.ocaml.org/u/n4323)\ **Post date:** [January 26, 2021, 11:43am UTC](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160/21 "2021-01-26T11:43:09Z")
Since @vlaviron was interested, I prepared a version that should be easy to clone and run locally (hopefully). If anyone would like to try it out, please PM me for a link. ---
**Author:** ![jjb](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/jjb/32/2713_2.png) [@jjb](https://discuss.ocaml.org/u/jjb)\ **Post date:** [January 26, 2021, 12:04pm UTC](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160/22 "2021-01-26T12:04:16Z")
Are you using landmarks via its ppx? If so, how sure are you that it does not interact with the `[@inline]` annotations? I would dig the ppx.exe command out of the dune log and rerun without `-dump-ast` to see the ocaml code post-preprocessing to check. ---
**Author:** ![n4323](https://avatars.discourse-cdn.com/v4/letter/n/97f17d/32.png) [@n4323](https://discuss.ocaml.org/u/n4323)\ **Post date:** [January 26, 2021, 12:27pm UTC](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160/23 "2021-01-26T12:27:27Z")
I’m not very sure. [This page](https://github.com/LexiFi/landmarks) describes the rewriting landmarks does in some detail. As I wrote in the OP, I did find consistent differences in program run-time also with landmarks disabled, though. [edit]: Ok, I generated the preprocessed output as you described; here is an example for the record version of `( - )`: ```ocaml let (-) { x; y } { x = x'; y = y' } = { x = (x -. x'); y = (y -. y') } [@@inline] include struct [@@@ocaml.warning "-32"] let (-) __x0__ x1 = Landmark.enter __generated_landmark_7d2008dabe15716a397ffdfecca952f2_25; (let r = try ((-) __x0)__x1 with | e -> (Landmark.exit __generated_landmark_7d2008dabe15716a397ffdfecca952f2_25; Landmark.raise e) in Landmark.exit __generated_landmark_7d2008dabe15716a397ffdfecca952f2_25; r) end ``` – I’m not quite sure how to interpret it. Does the included generated struct overwrite the definition in the first line? If yes, does that mean the `[@@inline]` annotation is lost? [edit 2] I just noticed that preprocessing with landmarks has an effect event if landmarks is not activated on running the program. Roughly, preprocessing by landmarks increases run-time by 30%. (And activating it at runtime, by a factor of 10 or so) In my current example, when landmarks preprocessing is on but instrumentation is off at runtime, the fastest tuple version is around 10% faster than the record version, and this appears to be reproducible. In contrast, without preprocessing, both are the same up to noise. ---
**Author:** ![n4323](https://avatars.discourse-cdn.com/v4/letter/n/97f17d/32.png) [@n4323](https://discuss.ocaml.org/u/n4323)\ **Post date:** [January 26, 2021, 12:30pm UTC](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160/24 "2021-01-26T12:30:00Z")
> [@dbuenzli](#): > > when I wrote [`gg`](https://erratique.ch/software/gg) which may be of interest to the OP This looks very similar to the record-based version. When records are returned from `( + )` and the like, they are constructed by an auxiliary function `v` defined as `let v x y = {x; y}`. Is that more than a notational convenience? [edit] > [@dbuenzli](#): > > [_Writing efficient numerical code in Objective Caml_] from the old caml site is still true (for non `flambda` compilers) This is an interesting read. I think I had read it at some point. My expectation was that nowadays with flambda, I could rely on small functions to all go away through inlining, so that I would not need to stick to the C-like style with big functions advocated there to get good performance. ---
**Author:** ![dbuenzli](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/dbuenzli/32/18_2.png) [@dbuenzli](https://discuss.ocaml.org/u/dbuenzli)\ **Post date:** [January 26, 2021, 12:59pm UTC](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160/25 "2021-01-26T12:59:47Z")
> [@n4323](#): > > This looks very similar to the record-based version. It _is_ the record based version. At the time I chose records over tuples and arrays of floats as it provides both unboxed floats and avoids bound checks on access. > [@n4323](#): > > they are constructed by an auxiliary function `v` defined as `let v x y = {x; y}` . Is that more than a notational convenience? No nothing more. It’s the constructor (assumed to be inlined in the implementation – nowadays a few `[@inline]` should likely be added). The `M.v` is my general convention to create **v** alues of an _immutable_ type `M.t` – it’s as close as you can get to a literal notation. ---
**Author:** ![vlaviron](https://avatars.discourse-cdn.com/v4/letter/v/ec9cab/32.png) [@vlaviron](https://discuss.ocaml.org/u/vlaviron)\ **Post date:** [January 26, 2021, 1:44pm UTC](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160/26 "2021-01-26T13:44:16Z")
> [@n4323](#): > > I just noticed that preprocessing with landmarks has an effect event if landmarks is not activated on running the program. Roughly, preprocessing by landmarks increases run-time by 30%. (And activating it at runtime, by a factor of 10 or so) Yes, the `[@inline]` annotation on the original function is kept but the `include ...` overrides the definition of `( - )` with a function that is not annotated with `[@inline]`. So it means that if the ppx is applied, it interferes strongly with the ability of the compiler to optimise. If it’s possible to switch to the “Benchmarking manually” mode of landmarks, I would advise you to do so (it will still have an impact on performance, but smaller, and it should interfere less with the compiler’s optimisations). ---
**Author:** ![gasche](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gasche/32/4_2.png) [@gasche](https://discuss.ocaml.org/u/gasche)\ **Post date:** [January 26, 2021, 2:31pm UTC](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160/27 "2021-01-26T14:31:21Z")
In adition to the effect of inliningn the addition of opaque side-effects in each subexpression would also severely limit the compiler’s ability to reorder or deduplicate computations. (I don’t realize how much of that is done by the optimizers today; there are few other valid simplifications on floating-point operations.) ---
**Author:** ![n4323](https://avatars.discourse-cdn.com/v4/letter/n/97f17d/32.png) [@n4323](https://discuss.ocaml.org/u/n4323)\ **Post date:** [January 26, 2021, 3:41pm UTC](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160/28 "2021-01-26T15:41:23Z")
I tried a version with the manual landmarks mode. For instance: ```ocaml let[@inline] ( - ) {x;y} {x=x';y=y'} = L.enter minus; let r = {x=x-.x'; y=y-.y'} in L.exit minus; r ``` This also seems problematic: It looks like `r` will get allocated, no matter if `( - )` is inlined as a whole and the fields of the record are used immediately afterwards. My current timings: - Completely without landmarks: tuple- and record- versions are equally fast. - Manual-mode annotated code without runtime instrumentation: tuple is faster than record by around 10%. - Manual-mode annotated code with runtime instrumentation: the tuple based version is faster than the record based version by a factor of two. This may be explained in part by allocation. E.g. `( + )` allocates ten times more in the record based version (!). The speed differences are probably due to how record/tuple construction, inlining and landmarks interact. - Automatic-mode preprocessed code without runtime instrumentation: same speed. - Automatic-mode with runtime instrumentation: tuple is 15% faster. Overall, unexpectely records are never better. Unfortunately, landmarks does not appear to be the tool of choice for micro-optimizing small functions. It seems to make sense only around chunks of code that run somewhat longer, so that messing with inlining isn’t as bad. ---
**Author:** ![gasche](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gasche/32/4_2.png) [@gasche](https://discuss.ocaml.org/u/gasche)\ **Post date:** [January 26, 2021, 3:54pm UTC](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160/29 "2021-01-26T15:54:38Z")
Yes, for micro-benchmarking I would use [core\_bench](https://github.com/janestreet/core_bench). ```auto let r = {x=x-.x'; y=y-.y'} in ``` Indeed, this will results in an allocation (of the record itself, not float boxing) in the naive execution of the OCaml program. Either you have faith in your optimizer (I would expect flambda to do fine, at least with the version that returns a record directly instead of let-binding it first), or you write slightly less abstract code where these pointwise operation are done by hand at the callsite (~ manual inlinine). I would probably choose the latter in a hot loop, to get robustness/predictability. ---
**Author:** ![vlaviron](https://avatars.discourse-cdn.com/v4/letter/v/ec9cab/32.png) [@vlaviron](https://discuss.ocaml.org/u/vlaviron)\ **Post date:** [January 26, 2021, 4:05pm UTC](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160/30 "2021-01-26T16:05:17Z")
> [@gasche](#): > > (I would expect flambda to do fine, at least with the version that returns a record directly instead of let-binding it first) Unfortunately Flambda cannot remove allocations of float records because they are compiled as arrays very early. I guess some work could be done to try to track immutable, known-length arrays, but that is unlikely to happen in the near future. ---
**Author:** ![n4323](https://avatars.discourse-cdn.com/v4/letter/n/97f17d/32.png) [@n4323](https://discuss.ocaml.org/u/n4323)\ **Post date:** [January 26, 2021, 4:15pm UTC](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160/31 "2021-01-26T16:15:08Z")
Another timing update: - Fully without landmarks, the full-program run-time differences reported earlier between the `_d2', _d2'', _d2'''` implementations seem to disappear (tuple version). - Fully without landmarks, the full-program run-time for the record version is marginally below that in the bullet point above. This is the first time that records appear to be a little faster, as expected. So part of the surprising results I posted above now look like user error: Preprocessing with landmarks interfered with inlining (even though it’s not activated at runtime). Sorry for the noise regarding that! [edit] For those using Landmarks, I found that a convenient way to use it in manual mode is to insert manual landmarks `L.enter` and `L.exit` points at few, not too-small functions, then define a do-nothing replacement module: ```ocaml module Landmark_off = struct let register _ = () let enter _ = () let exit _ = () end ``` and switch profiling on/off like so: ```ocaml module L = Landmark (*Landmark_off*) ``` This will completely eliminate calls to Landmarks after optimization including potential inlining obstructions as far as i can tell. ---
**Author:** ![gasche](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gasche/32/4_2.png) [@gasche](https://discuss.ocaml.org/u/gasche)\ **Post date:** [January 26, 2021, 4:33pm UTC](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160/32 "2021-01-26T16:33:49Z")
@vlaviron I don’t know about the compilation scheme for float-only records. Are they always compiled to generic arrays, or are they compiled as FloatArray when they are known to be float-only? The former would explain why @n4323 is not seeing any benefit to records, if testing on a `-no-flat-float-array` switch! ---
**Author:** ![nojb](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/nojb/32/519_2.png) [@nojb](https://discuss.ocaml.org/u/nojb)\ **Post date:** [January 26, 2021, 4:55pm UTC](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160/33 "2021-01-26T16:55:20Z")
> [@gasche](#): > > Are they always compiled to generic arrays, or are they compiled as FloatArray when they are known to be float-only? Unless I’m misremembering, records statically known to have only `float` fields are always compiled as “flat” blocks, even in `no-flat-float-array` mode. Cheers, Nicolas ---
**Author:** ![vlaviron](https://avatars.discourse-cdn.com/v4/letter/v/ec9cab/32.png) [@vlaviron](https://discuss.ocaml.org/u/vlaviron)\ **Post date:** [January 26, 2021, 4:57pm UTC](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160/34 "2021-01-26T16:57:34Z")
As far as I can tell they’re compiled as FloatArray (`Pmakearray (Pfloatarray, mut)`). It seems curious, but both versions could end up having roughly the same run time because the extra allocations from tuples + floats are matched by the extra record allocations when deconstructing a vector that has just been built (but that’s just a random guess). ---
**Author:** ![vlaviron](https://avatars.discourse-cdn.com/v4/letter/v/ec9cab/32.png) [@vlaviron](https://discuss.ocaml.org/u/vlaviron)\ **Post date:** [January 26, 2021, 7:03pm UTC](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160/35 "2021-01-26T19:03:07Z")
So I actually checked the code, and it turns out that flambda actually does track the contents of immutable float arrays, so the record allocations can actually disappear. Sorry for wrongly claiming the opposite earlier. (But in my defense, from looking at the code it’s a hack specific to float arrays, that was probably added only because float records ended up as arrays. For regular arrays nothing is tracked at all, even in the immutable case.) So the record version should always be faster than the tuple version, but with aggressive inlining it might be the case that we end up with so little allocations in both cases that the difference becomes lost in the noise. I’ll keep investigating… ---
**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:** [April 4, 2023, 8:31am UTC](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160/36 "2023-04-04T08:31:10Z")
If you send me a link, I’ll have a look at the code. [Previous page](https://discuss.ocaml.org/t/optimizing-small-vector-operations/7160.md?page=1)