Вычисление индекса блока и обьекта в нем по глобальному индексу обьекта

Размер блока определяется как "BlockSize = PageSize*BlockIndex".
"PageSize = 4096" но может быть и большей степенью двойки.
Размер обьекта (UnitSize) произвольный, но меньше или равно PageSize.
Так как BlockSize не всегда делится на UnitSize без остатка, то по формуле получается результат с накапливающейся ошибкой(Чем больше индекс блока, тем больше ошибка). Например когда "
UnitSize = 26"

Так считается индекс блока(С ошибкой, когда имеем остаток от BlockSize/UnitSize):

Код (Text):

1. size_t FindBlockForUnit(size_t UnitIndex, size_t UnitSize, size_t PageSize)
2. {
3. size_t UnitsOnPage = PageSize / UnitSize;
4. size_t S = (2 * UnitIndex) / UnitsOnPage;
5.  
6. size_t Discriminant = (4 * S) + 1;
7. size_t BlockIndex   = (std::sqrt(Discriminant) - 1) / 2;  
8. return BlockIndex;    
9. }

Эта функция тоже дает результат без учета потерянных байтов на конце каждого блока:

Код (Text):

1. size_t GetCumulUnitsForBlock(size_t BlockIndex, size_t UnitSize, size_t PageSize)
2. {
3. size_t BlockSize  = (PageSize * BlockIndex);
4. size_t CumulPages = (BlockIndex * (BlockIndex + 1)) / 2;    
5. size_t CumulBytes = PageSize * CumulPages;
6. size_t CumulUnits = CumulBytes / UnitSize;
7. return CumulUnits;
8. }

Последовательность остаточных байтов для блока повторяется каждые "size_t BlkRange = UnitSize / (1 << std::countr_zero(UnitSize)); "
Можно было бы сделать таблицу для коррекции но она сильно растет вместе с размером
UnitSize. Таблицы пришлось бы генериривать во время компиляции, а это очень замедлит сборку.

Это все нужно для быстрого доступа к обьекту в памяти по индексу, при том что в памяти они в разных блоках и есть только список этих блоков для нахождения по индексу. А тот, кто обращается к обьекту по индексу ни чего про блоки знать не должен.

В математике я не силен. Может есть способ вычислять все эти коррекции? Линейная алгебра, дифференциальные уравнения? ChatGPT в этом направлении шел, но запутался.

 

Несколько раз перечитал. Так и не понял что такое блок, почему его размер - функция от его номера и как вычисляя номер элемента в буфере можно выйти в квадратный трехчлен.

Вот здесь что-то безумное:
При UnitSize=26 BlkRange=26/2=13, но 4096=157*26 + 14.
При UnitSize=34 BlkRange=34/2=17, но 4096=120*34 + 16.
Если эти хвосты - выравнивания до размера страницы, то длина выравнивания =PageSize%UnitSize, а не этот содом.
Функцию с такими аргументами я вижу вот так:

Код (Text):

1. size_t FindBlockForUnit(size_t UnitIndex, size_t UnitSize, size_t PageSize)
2. {
3.     size_t UnitsPerPage=PageSize/UnitSize;
4.     size_t PageIndex=UnitSize/UnitsPerPage;
5.     return PageIndex;
6. }

Но это если отбросить загадочную и непонятную сущность по имени Block.

 

Ну так чатжпт, небось, подсказал, что динамический массив должен расти удваиваиванием текущего размера (ну или там newSize = currSize * 1.6).

Vicshann,
Не парься, просто выделяй блоки по 4096*unitSize, юзерам уже нормально так в уши насрано про развитие технологий и обоснованность резервирования 2ТБ на каждый процесс, так что они с готовностью закупаются этими вкусными планками по 128 гигов

 

У меня уже есть Uniform Выделение блоков, когда все блоки одного размера, есть Exponential, когда все блоки это степень двойки. Не хватает только линейного роста блоков, для полного комплекта
У Exponential та же проблема, но там всего 32 блока, просто сделал подсчет коррекциии во время компиляции, все же на С++ это у меня.
Проблема что размер блока это PageSize*BlockIndex, но количество обьектов в блоке не UnitsInPage*BlockIndex потомы что накапливаются остаточные байты в конце каждого блока. Если делать всегда "UnitsInBlock = UnitsInPage*BlockIndex" то накапливаются конкретно потерянные байты, очень ощутимо при большом UnitSize.

Может это прояснит дело LINK
Тамошние гуру прибили вопрос даже не вникая

 

Добавь к каждому блоку дворд, хранящий количество элементов в нем:

Код (C):

1. struct block_t
2. {
3.     uint32_t unitCount;
4.     void* units;
5.     ...
6. };
7.  

При создании нового блока инициализируешь счетчик:

Код (C):

1. block_t* create_block (uint32_t index, uint32_t pageSize, uint32_t unitSize...)
2. {
3.     block_t* block = new block_t;
4.     block->unitCount = (pageSize * (1 + index)) / unitSize;
5.     ...
6. }

Поиск блока по индексу юнита делаешь в цикле:

Код (C):

1. uint32_t block_for_unit (block_t* blocks, uint32_t count, uint32_t unitIndex, uint32_t* unitIndexInBlock...)
2. {
3.     uint32_t i;
4.  
5.     for (i=0; i<count && unitIndex < blocks[i].unitCount; unitIndex -= blocks[i++].unitCount)
6.         ;
7.  
8.     *unitIndexInBlock = unitIndex;
9.     return i;
10. }

Вангую, цикл с одним сравнением и одним вычитанием на массиве из миллиона элементов будет работать быстрее, чем куча умножений/делений/корней.

 

Vicshann
как насчет начать использовать СТЛ - std::vector/etc?

 

STL не вариант, как и все стандартные библиотеки
Кажется std::vector выделяет обьекты пачками, стандартным аллокатором. Там тоже, если нужно что-то спацифическое, то лучше уже свой аллокатор ему передавать.
У меня блоки берутся сразу от mmap/VirtualAlloc.
Циклы как бы нельзя, пусть и только при переходе границы блоков итератором требуются все эти вычисления. Иначе неприятный сюрприз с падением производительности при маленьких блоках.
А если там вообще дерево хранится, то полные тормоза, особенно если дерево перестраивалось.
Там может быть блоков на несколько гигабайт. Например, если размер страницы 64К, то 128мб это примерно 1000 блоков, то есть примерно 1000 итераций в цикле будет в конце.
У блоков действительно могут быть заголовки - еще одна причина почему блоки не делятся без остатка на обьекты

 

Сделал все сам, как обычно

Код (Text):

1. template<size_t UnitSize, size_t PageSize> struct SStrat
2. {
3. static constexpr const size_t UnitsOnPage = PageSize / UnitSize;
4. static constexpr const size_t BlkLftRange = UnitSize / (1 << std::countr_zero(UnitSize));    // Leftover bytes sequence repeat range (in blocks) // Same as "UnitSize / std::gcd(PageSize, UnitSize)"
5.  
6. struct SApArr  
7. {
8.   size_t TotalInRange;    
9.   size_t Arr[BlkLftRange+1];
10.   consteval SApArr(void)
11.    {
12.     size_t Total = 0;
13.     this->Arr[0] = Total;
14.     for(size_t i=1; i <= BlkLftRange; i++)
15.      {
16.       Total += (PageSize * i) % UnitSize;
17.       this->Arr[i] = Total;   // Cumulative bytes  
18.      }
19.     TotalInRange = Total;
20.    }
21. } static constexpr const CorrArr;
22. //------------------------------------------------
23. // NOTE: Does not considers leftover bytes accumulation error (Actual CumulBytes must be somehow <=)
24. static size_t GetCumulBytesForBlock(size_t BlockIndex)       // Offset For Block
25. {
26. size_t BlockSize  = (PageSize * BlockIndex);
27. size_t CumulPages = (BlockIndex * (BlockIndex + 1)) / 2;  
28. size_t CumulBytes = PageSize * CumulPages;
29. return CumulBytes;    // Requires leftover correction!
30. }
31. //------------------------------------------------
32. static size_t GetCumulUnitsForBlock(size_t BlockIndex)
33. {
34. size_t CumulUnits = GetCumulBytesForBlock(BlockIndex) / UnitSize;
35. return CumulUnits;    // Requires leftover correction!
36. }
37. //------------------------------------------------
38. static size_t FindBlockForUnit(size_t UnitIndex)
39. {
40. size_t FullGroups   = UnitIndex / UnitsOnPage;
41. size_t Discriminant = (8 * FullGroups) + 1;
42. size_t BlockIndex   = ((size_t)std::sqrt(Discriminant) - 1) / 2;
43. return BlockIndex;    // Requires leftover correction!
44. }
45. //------------------------------------------------
46. static size_t FindBlockForOffset(size_t UnitOffset)    // This should be used to find correction by a table
47. {
48. size_t FullPages    = UnitOffset / PageSize;
49. size_t Discriminant = (8 * FullPages) + 1;
50. size_t BlockIndex   = ((size_t)std::sqrt(Discriminant) - 1) / 2;
51. return BlockIndex;    // Requires leftover correction!
52. }
53. //------------------------------------------------
54. static size_t GetUnitForOffset(size_t UnitOffset)
55. {
56. return UnitOffset / UnitSize;
57. }
58. //------------------------------------------------
59. static size_t GetOffsetForUnit(size_t UnitIndex)    // As if in a single block
60. {
61. return UnitIndex * UnitSize;
62. }
63. //------------------------------------------------
64. static size_t CalcForIndex(size_t UnitIndex, size_t& Idx)
65. {
66. size_t uoffs = GetOffsetForUnit(UnitIndex);
67. size_t cbidx = FindBlockForOffset(uoffs);
68. size_t aidx  = (cbidx % BlkLftRange);    
69. size_t corra = ((cbidx / BlkLftRange) * CorrArr.TotalInRange);
70. size_t corrb = corra + CorrArr.Arr[aidx];
71. size_t corrc = corra + CorrArr.Arr[1+aidx];
72. size_t cbfix = FindBlockForOffset(uoffs + corrc);    // The square root again :(
73. size_t unfix = (GetCumulBytesForBlock(cbfix) - corrb) / UnitSize;
74. size_t ubidx = UnitIndex - unfix;
75. Idx = ubidx;
76. return cbfix;
77. }
78. //------------------------------------------------
79. static int LogTestBlocks(void)
80. {
81. size_t BlkIdx = 0;
82. size_t BlkIdxU = 0;
83. size_t UIdxInBlk = 0;
84. size_t BlkNextOffs = PageSize;
85. size_t BlkNextUnits = UnitsOnPage;
86. for(size_t uoffs=0,uidx=0;uoffs <= 0xFFFFFFFF;uidx++,UIdxInBlk++,uoffs+=UnitSize)
87.   {
88.    if(uoffs >= BlkNextOffs)BlkNextOffs += (PageSize * (++BlkIdx+1));        // To test FindBlockForOffset
89.    if(uidx  >= BlkNextUnits){BlkNextUnits += (PageSize * (++BlkIdxU+1)) / UnitSize; UIdxInBlk = 0;}
90.  
91.    size_t ubidx = 0;
92.    size_t cbfix = CalcForIndex(uidx, ubidx);
93.    size_t cbidx = FindBlockForOffset(uoffs);
94.    if(cbidx != BlkIdx)
95.      return -1;
96.    if(cbfix != BlkIdxU)
97.      return -2;
98.    if(ubidx != UIdxInBlk)
99.      return -3;
100.                                        
101.    printf("|%-14u|%-14u|%-14u|%-14u|%-14u|\n", (uint32_t)uidx, (uint32_t)cbidx, (uint32_t)cbfix, ubidx, UIdxInBlk);  
102.   }
103. printf("Done with blk %u",BlkIdx);
104. return 0;
105. }
106. //------------------------------------------------
107. };
108.  
109. using Strat26 = SStrat<26, 4096>;
110. Strat26::LogTestBlocks();

Может можно это как-то еще оптимизировать что бы поменьше квадратных корней было?