> именно с затратами О(1). Да ну?
https://sourceware.org/glibc/wiki/MallocInternals
> Malloc Algorithm
> If the request is "large", take a moment to take everything in the fastbins and move them to the unsorted bin, coalescing them as you go.
[...]
> Start taking chunks off the unsorted list, and moving them to small/large bins, coalescing as you go (note that this is the
> only place in the code that puts chunks into the small/large bins). If a chunk of the right size is seen, use that.
[...]
> In a nutshell, free works like this:
> If there is room in the tcache, store the chunk there and return.
[...]
> If the chunk is large enough, coalesce any fastbins and see if the top chunk is large enough to give some memory back to the system. Note that this step might be deferred, for performance reasons, and happen during a malloc or other call.
Магия, не иначе! И совсем никакой "сборки мусора" унутрях (про coalescing просто врут!)
А ведь могли взять какую-нибудь чисто академическую реализацию c константой c = "over 9000" (но формально оно будет в O(1)) или специфичную, правда, с офигенной фрагментацией (но ведь памяти сейчас все равно много, так что пофиг) :(
>> malloc/free
> а если ты, умник, считаешь, что ОС глупее тебя, - лезь пиши свои реализации, это несложно
«Смешались в кучу кони, люди,»
Я-то писал, поэтому как раз в курсе, что malloc/free не являются частью ОС.
И по-моему, странно считать набор (под)программ и алгоритмов умнее себя, любимого – но у всех свои странности.
Некоторые вон, вычитывают что-то между строк, считают, что malloc/free предоставляется им ОС и вообще похоже не в курсе, зачем используется прослойка "c наворотами" в виде malloc вместо прямого вызова mmap и почему столько копий было сломанно при поиске наилучшей реализации сишного динамического аллокатора: jemalloc, dlmalloc, tcmalloc и т.д.
