Provide fast robust primitives

[Chris00]

It would be nice if this library, "providing basic types for computer graphics", would have robust geometrical primitives.

[dbuenzli]

Do you have a more precise list in mind ?

[Chris00]

Yes, the two explained on the linked page: "orientation" (on what side of s straight line) and "in_circle".

[dbuenzli]

@Chris00 I need a robust orientation 2D test now :-) I think'll port the reference you pointed to since it seems quite popular.

I was just wondering if maybe there had been new results since then (a bit of my own search did not reveal anything interesting). One of my gripes is that this robust predicate needs scratch storage which will make our multicores unhappy. Allocating it on each test seems a bit too expensive (though it should still be measured at some point).

I'm thinking about scheme where you can allocate the scratch space and pass it explicitely something like:

type P2.orient_storage 
val P2.orient_storage : unit -> orient_storage
val P2.orient : ?orient_storage:orient_storage -> p2 -> p2 -> p2 -> float

So the function is thread unsafe by default, but if you have multiple threads accessing it you can allocate your own storage.

Any thoughts ?

[Chris00]

Hi,

On 6 October 2022 at 11:58 +02, Daniel Bünzli @.***> wrote:

@Chris00 I need a robust orientation 2D test now :-) I think'll port the reference you pointed to since it seems quite popular.

I was just wondering if maybe there had been new results since then (a bit of my own search did not reveal anything interesting).

Nothing came under my radar (but I did not investigate that subject much since then).

One of my gripes is that this robust predicate needs scratch storage […] I'm thinking about scheme where you can allocate the scratch space and pass it explicitely […] if you have multiple threads accessing it you can allocate your own storage.

Any thoughts ?

Sounds reasonable to me.

[dbuenzli]

So the function is thread unsafe by default, but if you have multiple threads accessing it you can allocate your own storage.

Any thoughts ?

That remains quite inconvenient though since it pushes the problem on the client of the library and propagates to other libraries (if any).

As far as domains are concerned we can use domain local storage, but we still need to isolate the domain threads. Maybe we can write the code that uses the scratch space so that it doesn't allocate (and thus no thread will context switch), it does sound very brittle though.

Can maybe someone like @gasche suggest something here (TLDR: a library function needs mutable scratch space to implement its service which will be too costly to allocate on each call how do we do it a concurrency safe manner) ?

(Another issue is that I can't claim to really understand the adaptive part of the code and I'm a bit uncomforable cargo culting the code, for now d9c6a7f7ec88d662ba469eeaa5d added a function I could understand)

[dbuenzli]

will be too costly to allocate on each call

Maybe that's a red herring though. The C code allocates it on the stack (the JavaScript port which I was reading at some point has it as globals).

Is the minor gc competitive with stack allocation ?

[dbuenzli]

Is the minor gc competitive with stack allocation ?

Answering my own question I guess it mostly is as far as allocating is concerned. The only problem is that you reach the young limit faster and algos like the boolean ops in Pgon2, use it fairly often.

[gasche]

If you want a global cache / scratch space that remains across calls, and you want to be Multicore-safe without synchronization, I guess the OCaml 5 solution would be to use domain-local storage. This way each new domain will allocate a new scratch space on first use, and use it thereafter, without synchronization.

Another option would be to have a pool of scratch spaces available in a concurrent queue/bag. When the queue is empty, allocate a new scratch space. I know Domain.DLS which is readily available in the standard library, and I am less familiar with the library space for concurrent data structures. I think the "lockfree" library has something suitable. (In most workflows we don't need lock-free which adds un-needed complexity, but people implemented this first because it was more challenging.)

This being said, allocating local storage on each call is probably fairly fast (the OCaml GC is of the order of gigabytes per second).

Is the minor gc competitive with stack allocation ?

Yes for short-lived values, with the caveat that it will collect more often and thus incur some "false promotions" (some values that are fairly-short-lived end up on the major heap). One can compensate by increasing the minor heap size (to decrease promotion rate accordingly), at the cost of increased latency.

[dbuenzli]

Thanks @gasche.

If you want a global cache / scratch space that remains across calls, and you want to be Multicore-safe without synchronization, I guess the OCaml 5 solution would be to use domain-local storage.

But isn't that half of the story ? The threads in each domain will also compete for that domain local storage.

This being said, allocating local storage on each call is probably fairly fast (the OCaml GC is of the order of gigabytes per second).

Yeah my worry is also the js_of_ocaml path (seing that the JavaScript implementation used globals). Anyways I suspect the best is to start doing that first and then measure.