litceysel.ru
добавить свой файл
1
HATs: Hashed Array Trees


September 1996 Dr. Dobb's Journal

By Edward Sitarski

Edward is vice president of R&D at Numetrix Ltd. He can be reached at ed@tor.numetrix.com.


Arrays are the most natural and convenient data structure for a great many applications. They provide constant access time to their elements and are the structure of choice for many practical algorithms. Most commercial C++ toolkits offer a variable-length array container class, and probably millions of C++ programs use variable-length arrays as their core data structures. Increasing the size of a variable-length array by appending to the end is a common operation; if we knew the size of the array at the start then there would be no reason to use a variable-length array.

Массивы - наиболее естественная и удобная структура данных для очень многих приложений. Они обеспечивают постоянное время доступа к их элементам и эта структура выбора для многих практических алгоритмов. Большинство коммерческих комплектов инструментальных средств C++ предлагает контейнерный класс переменной длины массива, и возможно миллионы программ C++ используют переменной длины массивы как их основные структуры данных. Увеличение размера переменной длины массива, конкатенируя к концу - общая операция; если мы знали размер массива в начале затем не будет иметься никакой причины использовать переменной длины массив.

I became painfully aware of the limitations of most implementations of variable-length arrays when investigating some code that read the results of a database query. There was no way to determine the number of rows returned from the query beforehand, and the code used a commercial variable-length array class to store the data. The profiler told me that the array class was doing an incredible amount of element copying when resizing. This copying was taking much more time than the slow data transfer from the database!

Я глубоко познал ограничения большинства реализаций переменной длины массивов при исследовании некоторого кода, который читает результаты запроса к базе данных. Не имелось никакого способа определить число строк, возвращаемых из запроса заранее, и код использовал класс коммерческий переменной длины массива, чтобы сохранить данные. Профилировщик сообщил мне, что класс массива делал невероятное количество копирования элементов при изменении размеров. Это копирование занимало намного больше время чем медленная передача данных из базы данных!


You might argue that another data structure, such as a linked list, would have been more appropriate for this application, but it was too difficult to fix all the old code. I decided to try to implement a better performing array class that had the same interface as the old one.

Вы могли бы спорить, что другая структура данных, типа связанного списка, будет более соответствующая для этого приложения, но было слишком трудно переделать весь старый код. Я решил пробовать выполнять более эффективный класс массива, который имел тот же самый интерфейс как старый.

Many implementations of variable-length arrays leave much to be desired. Specifically, the function that appends to the end of the array can cause a large performance problem. Example 1 shows just about the worst way to do it. There are two main reasons why this implementation is so bad.

Много реализаций переменной длины массивов оставляют желать лучшего. Специально, функция, которая конкатенирует новые элементы в конец массива, может вызывать большую проблему с эффективностью. Пример 1 показывает примерно самый плохой способ делать это. Имеются две основные причины, почему эта реализация настолько плоха.



  1. Excessive element copying. If you add 1000 elements to the array, the internal loop will copy the old elements into newTArray each time the array expands, a total of over 500,000 copy operations. This seemingly innocent code is doing about 500 times more assignments than necessary for the 1000 elements, and it only gets worse as the array grows. This implementation is O(N2) (the same time complexity as Bubblesort) and highly inefficient even for small arrays.
  2. Чрезмерное копирование элементов. Если Вы добавляете 1000 элементов к массиву, внутренний цикл копирует старые элементы в newTArray, каждый раз массив расширяется, общее количество более чем 500,000 операций копирования. Этот по-видимому невинный код делает приблизительно более 500 раз присвоений чем необходимо для 1000 элементов, и только становит хуже, поскольку массив растет. Эта реализация - O(N2) (та же самая зависимость от времени как для Bubblesort) и высоко неэффективная даже для малых массивов.


  3. Excessive memory usage. During the copy operation, both the existing array and the new array must be present in memory at the same time, doubling the memory requirement of the array. Worse, each time the array grows, it creates a memory fragment: the old array. This fragment cannot be reused the next time the array grows because the new array is larger and will not fit, as shown in Figure 1. This can increase the memory requirements by almost another factor of two.

  4. Чрезмерное использование памяти. В течение операции копирования, и существующий массив и новый массив должен присутствовать в памяти в то же самое время, при удвоении требования памяти массива. Хуже, каждый раз массив растет, это создает фрагмент памяти: старый массив. Этот фрагмент не может многократно использоваться, в следующий раз массив растет, потому что новый массив больший и не будет удовлетворять, как показано в 1 Рисунке. Это может увеличивать требования памяти на почти другой коэффициент два.



Figure 1: Memory usage during array resizing.


void vArray::append( T &el )

{

// Extremely bad implementation of

// variable length array.

T *newTArray = new T [numElements+1];

for(size_t j = 0; j < numElements; j++)

newTArray[j] = tArray[j];

delete tArray;

tArray = newTArray;

tArray[maxElements++] = el;

}

Example 1: A bad way to resize an array.

It is interesting to note that C's realloc() function does not have such severe problems. The reason is that once the array is large enough, it will be allocated from the end of the heap. realloc can then expand the buffer by increasing the size of the memory block without having to copy the data. Unfortunately, this does not work with C++ because realloc cannot call constructors on the expanded memory. C++ requires us to copy the elements explicitly.


Интересно обратить внимание, что C's realloc() функция не имеет таких серьезных проблем. Причина - то, что, если только массив является достаточным большим, он будет распределен с конца кучи. realloc может затем расширять буфер, увеличивая размер блока памяти, без необходимости копировать данные. К сожалению, это не работает в C++, потому что перераспределение не может вызывать конструкторы в расширенной памяти. C++ требует, чтобы мы копировали элементы явно.

You might try to address these problems by growing the array by more than one element at a time. However, this does not significantly reduce the memory usage. Even though it reduces the total number of copies, it is still an O(N2) algorithm -- all you've done is decrease the running constant. For example, if you add 1000 elements and grow the array by 10 elements whenever it's full, you are still performing 10+20+..+1000 = 50,500 copy operations, which is still O(N2). Although this is 10 times less copying than before, it is still 50 times more copying than is necessary.

Вы могли бы пробовать решить эти проблемы, прибавляя к массиву больее чем одни элемент одновременно. Однако, это не значительно уменьшает использование памяти. Даже при том, что это уменьшает общее число копирований, это - все еще O(N2) алгоритм - все, что вы сделали - уменьшение выполняющаяся константа. Например, если Вы добавляете 1000 элементов и наащиваете массив 10 элементами всякий раз, когда он полон, Вы все еще выполняете 10 + 20 + .. + от 1000 до 50,500 операций копирования, который является все еще O(N2). Хотя это - меньшее количество 10 раз копирований чем прежде, это - все еще в 50 раз больше копирований чем, необходимо.


HATs Usually Append in O(1) Time - HAT Обычно добавления O (1) Времени

To overcome the limitations of variable-length arrays, I created a data structure that has fast constant access time like an array, but mostly avoids copying elements when it grows. I call this new structure a "Hashed-Array Tree" (HAT) because it combines some of the features of hash tables, arrays, and trees.


Чтобы преодолевать ограничения переменной длины массивов, я создал структуру данных, которая имеет быстрое постоянное время доступа подобно массиву, но обычно избегает копирования элементов, когда она растет. Я вызываю эту новую структуру " Дерево хэшированого - массива " (HAT), потому что это объединяет некоторых из возможностей хэш - таблиц, массивов, и деревьев.

Although used to implement one-dimensional arrays, HATs are really two-dimensional; see Figure 2. A HAT consists of a Top array and a number of Leaves which are pointed to by the Top array. The number of pointers in the Top array and the number of elements in each Leaf is the same, and is always a power of 2.

Хотя используется, чтобы выполнить одномерные массивы, HAT действительно двумерны; см. Рисунок 2. HAT состоит из Главного массива и ряда Листьев, которые указаны от Главного массива. Число указателей в Главном массиве и числе элементов в каждом Листе - тот же самое, и - всегда степень двух.


Figure 2: HAT data structure.

Because the Top and Leaf arrays are powers of 2, you can efficiently find an element in a HAT using bit operations; see Example 2. Usually, appending elements is very fast since the last leaf may have empty space. Less frequently, you'll need to add a new leaf, which is also very fast and requires no copying.

Потому что Главная часть и массивы Листа - степени 2, Вы можете эффективно находить элемент в HAT, используя разрядные операции; см. Пример 2. Обычно, конкатенация элементов очень быстра, так как последний лист может иметь пустое пространство. Менее часто, вы будете должны добавить новый лист, которое является также очень быстрым и не требует никакого копирования.


inline size_t Hat::topIndex(const size_t j ) const

{

// Get the high index.

return j >> power;

}


inline size_t Hat::leafIndex(const size_t j ) const

{

// Get the low index.

return j & ((1<


}

inline T &Hat::operator[](const size_t j) const

{

// Return an element in the HAT. Do no bounds checking.

return top[topIndex(j)][leafIndex(j)];

}

Example 2: Fast indexing with bit operations.

When the Top array is full, it becomes a bit more interesting. My implementation first computes the correct size (Top and Leaf arrays are the same size, both a power of 2), then copies the elements into a new HAT structure, freeing the old leaves and allocating new leaves as it goes.

Когда Главный массив полон, это становится немного более интересным. Моя реализация сначала вычисляет правильный размер (Главная часть, и массивы Листа - тот же самый размер, оба степени 2), затем копирует элементы в новую структуру HAT, освобождая старые листья и рапределяя новые листья, как это идет.

This approach dramatically avoids most of the element copying performed by the previous array implementation. Recopying only occurs when the Top array is full, and this only happens when the number of elements jusrt exceeds the square of a power of 2. If N=4n, then the total amount of recopying is 1+4+16+64+256+...+N. Using the identity (x(n+1)-1)=(x-1) (1+x+x2+x3+... + xn) you have 1 +4+42+43+...+4n = (4(n+1) -1)/(4-1) = (4N-1)/3, or about 4/3 N. This means that the average number of extra copy operations is O(N) for sequentially appending N elements, not O(N2).

Этот подход избегает драматичного копирования большинства элементов в предыдущей реализацией массива. Перекопирование только происходит, когда Главный массив полон, а это только случается, когда число элементов превышает квадрат степени 2. Если N=4n, то общая сумма перекопирования 1+4+16+64+256+...+N. При использовании тождества (x(n+1)-1)=(x-1) (1+x+x2+x3+... + xn) Вы имеете 1 +4+42+43+...+4n = (4(n+1) -1)/(4-1) = (4N-1)/3, или около 4/3 N. Это означает это, среднее число дополнительных операций копирования - O(N) для последовательных конкатенации N элементов, не O(N2).


The technique of reallocating and copying each leaf one at a time also significantly reduces the memory overhead. Instead of needing memory for a complete copy of the HAT, you only need enough memory for an extra leaf. Because the leaf size depends on the square root of N, the extra memory required during resizing decreases dramatically as a percentage of N. For example, if you added 1,000,000 elements to the HAT, the extra memory needed for the last resize would be 1024 elements or about 0.1 percent of the memory already used for the array's data.

Методика перераспределения и копирования каждого листа по одному также значительно уменьшает непроизводительные затраты памяти. Вместо нуждающийся в памяти для полной копии HAT, Вы только нуждаетесь в достаточной памяти для дополнительного листа. Потому что размер листа зависит от квадратного корня N, дополнительная память, требуемая в течение изменения размеров уменьшается с драматичного как процент от N. Например, если Вы добавили 1,000,000 элементов к HAT, дополнительная память, необходимая для последнего изменяет размеры, было бы 1024 элементов или приблизительно 0.1 процентов от памяти, уже используемой для данных массива.

In addition, memory fragmentation is reduced. Since the Top and Leaf sizes always increase to the next power of 2, the heap manager may be able to combine two freed leaves from the smaller HAT to allocate a leaf in the larger one.

Кроме того, фрагментация памяти уменьшена. Так как Главная часть и размеры Листа всегда увеличивается к следующей степени 2, программа управления динамической областью может быть способна объединить двух освобожденных листов из меньшей HAT, чтобы распределить лист в большем.

Available electronically is code for a HAT template that includes some further optimizations to eliminate copying when the HAT grows and shrinks across resize boundaries. This is achieved at some expense of potential memory fragmentation, but results in smoother performance. The implementation allows the Top array to increase as a multiple of its former ideal size until an up or down threshold is reached.


Доступный с помощью электроники - код для шаблона HAT, который включает некоторую дальнейшую оптимизацию, чтобы устранить копирование, когда HAT наращивается и сжимается поперек изменения размера границ. Это достигнуто за некоторого расхода потенциальной фрагментации памяти, но приводит к более гладкой эффективности. Реализация позволяет Главному массиву увеличиваться как множитель вышеупомянутого идеального размера, пока вверх или вниз порог не достигнут.

Even if resizing is not an issue, this implementation has other advantages. For example, in a 16-bit environment, no object on the heap can exceed 64 KB. A HAT can manage arrays much larger than this without any single leaf exceeding 64 KB. You could also extend HATs to automatically swap leaves to and from disk storage to support truly huge arrays with a minimal memory footprint. Finally, there may be advantages to extending HATs to three or more levels rather than the two levels I've used.

Даже если изменение размеров - не проблема, эта реализация имеет другие преимущества. Например, в 16-разрядной среде, никакой объект в куче не может превышать 64 КБ. HAT может управлять массивами намного больше чем это без любого одиночного листа, превышающего 64 КБ. Вы могли бы также расширять HAT, чтобы автоматически менять местами листья в памяти и в памяти на диске, чтобы поддерживать огромные массивы в минимальной сетке памяти. В заключение, могут иметься преимущества для расширенных HAT в три или большего количества уровней лучше чем два уровня, которые я использовал.


Memory Overhead - Расход памяти

I've already suggested that HATs use much less memory than the standard approach of reallocating and copying the entire array. To see how much less, I'll compute the actual memory overhead of a HAT resize.

Я уже предложил, чтобы HAT использовали намного меньше памяти чем стандартный подход перераспределения и копирования всего массива. Чтобы видеть сколько меньше, я буду вычислять фактические непроизводительные затраты памяти для HAT, при изменении размеров.


The worst case happens when the elements in the HAT are the same size as pointers and the number of elements is one greater than a resize value. If the elements are the same size as pointers, you can add the unused portion of the Top array to any wasted memory in the Leaves, thus maximizing the amount of wasted memory as a percentage of the data in the array; see Table 1. You can see that as the HAT grows, the percentage of wasted memory in the worst case drops dramatically. Generally, the worst-case memory waste is (top+leaf-1)