Тема Аллокаторов частенько всплывает на просторах интернета: действительно, аллокатор — эдакий краеугольный камень, сердце любого приложения. В этой серии постов я хочу в подробностях рассказать о одном весьма занимательном и именитом аллокаторе — JeMalloc, поддерживаемый и развиваемый Facebook и используемый, например, в bionic[Android] lib C.
В сети мне не удалось найти каких-либо подробностей, полностью раскрывающих душу данного аллокатора, что по итогу сказалось на невозможности сделать какие-либо выводы о применимости JeMalloc при решении той или иной задачи. Материала вышло очень много и, дабы читать его было не утомительно, начать предлагаю с основ: Базовых Структур Данных используемых в JeMalloc.
Под катом рассказываю о Pairing Heap и Bitmap Tree, формирующих фундамент JeMalloc. На данном этапе я не затрагиваю тему многопоточности и Fine Grained Locking, однако, продолжая серию постов, обязательно расскажу про эти вещи, ради которых, собственно, и создается разного рода Экзотика, в частности и та, что описывается ниже.