memory fragmentation

[gjaegy]

Hi Angus,

I'm having a little request: in our use case, we process a lot of geometry using your great library. However, memory get fragmented at some point, one of the main reason being the new[] call at the beginning of ClipperBase::AddPaths().

I'm not sure however how to solve that issue.

As for the context, our code use chunked arrays for big containers (basically, a std::vector in chunks, where each chunks is lesser than a threshold, using a special allocator this avoid fragmentation). It would be easy to plugin if the code in the loop below was using indices (into the container) rather than pointers.

I could modify the AddPaths() method and change the code in the loop after that allocation, so that the algorithm uses indices rather than pointers and pointers arithmetics (this would allow plugin any containers that has a [] operator), however, this would mean quite a few differences from the head version, making future merge harder to do.

What is your feeling about that ? Do you see maybe a better solution to get rid of that raw buffer allocation, that can get quite big in some cases ?

Thanks for any input !

[alexisnaveros]

Yup, I remember seeing a 15% boost by replacing all new/delete with slab allocators in my C port. There's way too much overhead and cache trashing with new/delete of tiny chunks.

This definitely should be considered on the C++ side too.

EDIT: I guess I was mostly waiting for the whole algorithm to be considered "stable", no more bug fixes or horizontal issues, before proposing all these lower level improvements. Same for complex high-level scalability improvements (it's currently pretty terrible with shapes with billions of edges).

[AngusJohnson]

What is your feeling about that ? Do you see maybe a better solution to get rid of that raw buffer allocation, that can get quite big in some cases ?

Thanks for the feedback and suggestion. I would have responded earlier but I've been totally occupied with getting the latest Beta version finished, and it almost is now (though the latest iteration needs to be translated into C#).

But of course I'm keen to optimise the code as much as possible (without resorting to extreme measures that would massively bloat and complicate the code). My working assumption has been that using pointers eg to next/previous in linked lists (rather than indicies) would be more efficient even though they're stored in arrays (ie vector<>s). And I accept that this assumption could well be wrong. If you were happy to test changing pointers to indicies and confirrm that it does significantly improve performance I would be very happy to adopt your modifications.

[gjaegy]

Hi Angus,

No worry, thanks for getting back to me. Actually I've managed to solve my issue by using another allocator (stack-like) to resolve my fragmentation issue, so there is no rush anymore.

Anyway, I'm happy to help improving this library as it is really useful to me.

The purpose of my post was to modify that function so that it works without assuming the "vertices" are stored contiguously in memory. This would allow users to replace (if needed) that "new[]" with any container of their choice (as long is it offers a [] operator).

Regarding performance, nothing can be raw pointers performance-wise. However, using indices won't slow down the process significantly, as memory access pattern remains unchanged. Having an additional pointer arithmetic operation (+) in that code won't really hurt, as memory latency is likely to be the bottleneck.
I'll have a look and see how that function can be modified so that indices are used rather than direct access to that memory block through pointers, I'll get back to you when done.