5

Standard allocators can optionally hints as default parameters 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?

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 cpu or gpus, I am trying to see good or proven code that used this hint parameter internally, presumably efficiency and for particular types of memory. Even if it is some exotic system.

Note 2: I am not asking how/if/what to pass as 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.

alfC
  • 14,261
  • 4
  • 67
  • 118
  • 1
    why leaving aside that it is deprecated? If there were good use cases, it wouldnt be deprecated, no? – 463035818_is_not_an_ai Mar 17 '21 at 09:16
  • 2
    Does this answer your question? [Does an allocation hint get used?](https://stackoverflow.com/questions/15380318/does-an-allocation-hint-get-used) – underscore_d Mar 17 '21 at 09:18
  • @underscore_d 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). – alfC Mar 17 '21 at 09:28
  • 1
    @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. https://en.cppreference.com/w/cpp/memory/allocator_traits/allocate – alfC Mar 17 '21 at 09:32
  • 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" – 463035818_is_not_an_ai Mar 17 '21 at 09:33
  • As of C++20, the [`std::allocator::allocate()`](https://en.cppreference.com/w/cpp/memory/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. – oraqlle Aug 29 '22 at 10:06
  • @oraqlle 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. – alfC Aug 30 '22 at 16:37
  • 2
    Well, after a bit of research, I found at least an [academic paper](https://doi.org/10.1145/1542431.1542447) (corresponding [dissertation](https://core.ac.uk/download/pdf/4277049.pdf)) 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](https://github.com/johannesthoma/mmap_allocator) library does not do so). – Sedenion Aug 30 '22 at 19:58
  • @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? – alfC Aug 30 '22 at 22:25

1 Answers1

2

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.

Sedenion
  • 5,421
  • 2
  • 14
  • 42
  • wayback link: https://web.archive.org/web/20160629161450/http://parasol.tamu.edu/resources/downloads.php – alfC Aug 31 '22 at 21:14
  • Yes, I checked the web archive, too, but I still could not find the source there. Or am I missing something obvious? – Sedenion Sep 01 '22 at 05:33
  • no, i was just hoping you would know how to navigate the archived page. i couldn’t. – alfC Sep 02 '22 at 02:47
  • Clicking on the links in the archived page works for me, but unfortunately no source code anywhere :-( – Sedenion Sep 02 '22 at 05:30