Example uses of hint parameter in the implementation of an allocator

Question

Standard allocators can optionally take a hint as a second parameter https://en.cppreference.com/w/cpp/memory/allocator/allocate

T* allocate( std::size_t n, const void * hint);

Leaving aside that this is formally deprecated in C++20 (which apparently doesn't mean that an allocator cannot have the hint argument):

Do you know of good uses of the hint in standard or non-standard allocator implementations in existing code or theoretical code? Or is it a plain historical relic?

For context, I am trying to understand if the current hint can help with allocating when you have more than one device (e.g. GPU).

Note 1: I am not asking how to allocate memory in CPUs or GPUs; I am trying to see good or proven code that uses this hint parameter internally, presumably for efficiency and particular types of memory. Even if it is some exotic system.

Note 2: I am not asking how/if/what to pass as an argument of hint (i.e., "just pass the current pointer of your container"), like in the linked question. I am asking from the point of view of someone implementing a custom allocator.

Thoroughfare

why leaving aside that it is deprecated? If there were good use cases, it wouldnt be deprecated, no? – Calyptra

Does this answer your question? Does an allocation hint get used? – Golter

@Golter mmm, thanks for the link. the only concrete case is the first answer (colony). It seems that it used the hint of std allocator blindly and got better performance simply doing that. I am asking from the point of view of an implementor of an allocator (e.g. of special memory, for example shared memory, mapped memory or gpu). – Thoroughfare

@largest_prime_is_463035818 apparently for allocators, deprecation doesn’t mean that the feature is removed but that the feature is not required in order to be a standard-like allocator. For example, allocator traits will keep takin the hint. And ignore it if it can not be passed. en.cppreference.com/w/cpp/memory/allocator_traits/allocate – Thoroughfare

thanks now I understand. Seems like I just didnt get the meaning of "which apparently doesn't mean that an allocator cannot have the hint" – Calyptra

As of C++20, the std::allocator::allocate() hint overload was removed but cppreference said it was used to hint a nearby memory location so maybe it was used for caching performance or in embedded systems/memory constrained contexts when you want to localize memory allocations. – Throat

@Throat yes, it was removed from std allocator because probably no CPU platform was using it. However allocator_traits still has it, so a custom allocator can still use it so it could still be relevant. incidentally polymorphic_allocators doesn’t seem to define an interface with hint. – Thoroughfare

Well, after a bit of research, I found at least an academic paper (corresponding dissertation) that apparently uses the hint parameter with some success to write a more locality aware allocator. Unfortunately, the source code seems to be lost. The paper is cited by a bunch of others, but I have not checked if they actually use it. Otherwise, I guess one could pass the hint parameter to mmap (although e.g. this library does not do so). – Maddalena

@Sedenion. this is the type of reference i was looking for even if the code is lost. interesting they found fragmentation increases. I guess when you are constrained to look for locality this is what happens. care to convert the comment into an answer? – Thoroughfare

Answer 1

Work by Alin Jula and Lawrence Rauchwerger

The paper "Two memory allocators that use hints to improve locality" by Alin Jula and Lawrence Rauchwerger from 2009 introduces

Two locality improving allocators that can use allocation hints provided from the C++ STL library and outperform state-of- the-art allocators, such as dlmalloc and PHKmalloc, by an average of 7%, and 17% respectively, while yielding memory fragmentation as low as dlmalloc’s.

They call the allocators "TP" and "Medius" and they use use the allocate()'s hint parameter to try and allocate the memory near the hint to improve data locality. To this end, they modified the containers in gcc's stdlibc++ to actually pass hints to the allocators. The corresponding dissertation by Alin Jula is available for free.

The work is preceded by "Custom Memory Allocation for Free" from 2006 by the same authors, which introduces the allocator "Defero". It apparently uses the same interface (i.e. the hint parameter of the allocate() function).

Unfortunately, the link to the source code (http://parasol.tamu.edu/resources/downloads.php) is dead and I was not able to find them online. However, L. Rauchwerger seems to be still around and maybe he might be willing to share the source if you contact him.

Using the hint for mmap

The mmap() function allows to provide a hint address for the memory. I was able to find some source (author's website) that actually does this:

namespace leimyalloc {
  template <typename T>
  class mmap_allocator {
    // ...
    pointer allocate (size_type num, void *  hint = 0) {
      pointer p = (pointer) ::mmap(hint, num, PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE, -1, 0);
      int * val = (int *)p;
      if(val == MAP_FAILED)
        p = 0;
      return p;
    }
    // ...
  };
}

However, I could not find if anyone actually uses it.

Searching for "mmap allocator" gives for example this and this github project, but they simply ignore the hint parameter.

Maddalena

wayback link: web.archive.org/web/20160629161450/http://parasol.tamu.edu/… – Thoroughfare

Yes, I checked the web archive, too, but I still could not find the source there. Or am I missing something obvious? – Maddalena

no, i was just hoping you would know how to navigate the archived page. i couldn’t. – Thoroughfare

Clicking on the links in the archived page works for me, but unfortunately no source code anywhere :-( – Maddalena