ЕКСПЕРИМЕНТАЛЬНЕ ДОСЛІДЖЕННЯ МЕТОДІВ ПОШУКУ В АВЛ-ДЕРЕВІ З УРАХУВАННЯМ ІЄРАРХІЇ ПАМ'ЯТІ
DOI:
https://doi.org/10.26906/SUNZ.2026.3.131Ключові слова:
АВЛ-дерево, розміщення Ейтцінгера, алгоритми пошуку, програмне попереднє завантаження даних, кеш-пам'ять, локальність даних, BenchmarkDotNet, експериментальна оцінка продуктивностіАнотація
Актуальність. Дослідження впливу просторової локальності даних, передбачення розгалужень та програмного попереднього завантаження даних на продуктивність пошуку становить значний інтерес при розробці високопродуктивних структур даних. Предмет дослідження: методи пошуку в АВЛ-дереві, представленому у вигляді масиву з використанням розміщення Ейтцінгера, та вплив ієрархії пам'яті процесора на їхню швидкодію. Мета дослідження: експериментально оцінити ефективність різних методів пошуку в АВЛ-дереві з поданням на масивах залежно від розміру масиву та положення робочого набору даних щодо рівнів ієрархії пам'яті процесора. Завдання дослідження. Реалізувати та експериментально дослідити алгоритми пошуку Binary, AVL, Eytzinger, EytzingerB та EytzingerBP; визначити діапазони розмірів масивів, які відповідають різним рівням ієрархії пам'яті; порівняти швидкодію досліджуваних алгоритмів; встановити вплив просторової локальності даних, помилок передбачення розгалужень та програмного попереднього завантаження даних на ефективність пошуку. Методи дослідження. Використані методи алгоритмічного аналізу, експериментального дослідження продуктивності програмного забезпечення та статистичної обробки результатів вимірів. Експериментальна оцінка виконана засобами BenchmarkDotNet на платформі .NET 8 з використанням апаратних лічильників продуктивності процесора. Результати дослідження. Встановлено, що ефективність алгоритмів пошуку визначається як їх обчислювальної складністю, а й особливостями взаємодії з ієрархією пам'яті процесора. Показано, що при розміщенні робочих даних у кешах L1/L2 найменший час пошуку забезпечує алгоритм EytzingerB, тоді як при переході до даних, розміщених у кешах L3 та оперативної пам'яті, найкращі результати демонструє алгоритм EytzingerBP, який використовує програмне попереднє завантаження даних. Отримано експериментальні залежності часу пошуку від розміру масиву, визначено галузі ефективного застосування досліджуваних алгоритмів та кількісно оцінено виграш найефективніших методів пошуку. Експериментально встановлена зміна найефективнішого алгоритму пошуку при переході робочих даних між рівнями ієрархії пам'яті процесора: у діапазоні L1/L2 мінімальний час пошуку забезпечує алгоритм EytzingerB, тоді як у діапазоні L3 та оперативної пам'яті лідирує алгоритм EytzingerBP. Висновки. Подання АВЛ-дерева в масиві Ейтцінгера забезпечує істотне підвищення швидкодії пошуку в порівнянні з класичною реалізацією дерева на покажчиках. Експериментально підтверджено, що вибір оптимального методу пошуку визначається рівнем ієрархії пам'яті, в якому знаходиться робочий набір даних. Отримані результати можуть бути використані для проектування високопродуктивних пошукових структур даних та оптимізації алгоритмів пошуку для сучасних багаторівневих підсистем пам'яті.Завантажити
Посилання
1. Knuth, D. (1997), The Art of Computer Programming. Sorting and Searching, vol. 3, Addison-Wesley, 2nd edition, 780 p., available at: https://www.scribd.com/document/438657664/The-Art-Of-Computer-Programming-Sorting-and-Searching-2ndedition-Volume-3-pdf
2. Knuth, D. (2010), Selected papers on design of algorithms, vol. 7, Stanford, California, 453 pp., available at: https://press.uchicago.edu/ucp/books/book/distributed/S/bo8930293.html
3. Sedgewick R., and Wayne K., (2024), Algorithms, 4nd edition, Princeton University, Addison-Wesley, 955 p. available at: https://algs4.cs.princeton.edu/home/
4. Cormen, H. Тhоmаs, Leiserson, Е.Charles, and Rivest, L. Ronald (2022), Clifford Stein. Introduction to algorithms, MIT Press, 1312 p., available at: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
5. Wiener, R. (2022), “AVL Trees”, Generic Data Structures and Algorithms in Go: An Applied Approach Using Concurrency, Genericity and Heuristics, Apress, Berkeley, CA, pp. 315–347, doi: https://doi.org/10.1007/978-1-4842-8191-8_10 DOI: https://doi.org/10.1007/978-1-4842-8191-8_10
6. Drepper, U. (2007), What every programmer should know about memory, 114 р., available at: https://akkadia.org/drepper/cpumemory.pdf
7. Pikus, F. G. (2021), The Art of Writing Efficient Programs, Packt Publishing, Birmingham, 445 p., available at: https://ivms.com.safespacenj.org/Tech_Books/writ%20eff%20pgms.pdf
8. (2024), Intel® 64 and IA-32 Architectures Optimization Reference Manual, vol. 1, Order Number 248966-049, available at: https://cdrdv2-public.intel.com/814198/248966-Optimization-Reference-Manual-V1-049.pdf
9. (2026), Intel® 64 and IA-32 Architectures Software Developer's Manual Combined, vol. 2, Instruction Set Reference Order Number 325383-092US, available at: https://cdrdv2.intel.com/v1/dl/getContent/671110
10. (2026), Intel® 64 and IA-32 Architectures Software Developer's Manual Combined, vol. 3, System Programming Guide, 182 p., available at: https://cdrdv2.intel.com/v1/dl/getContent/671447
11. Fog, A. (2026), Optimizing software in C++: An optimization guide for Windows, Linux and Mac platforms, available at: https://www.agner.org/optimize/optimizing_cpp.pdf
12. Fog, A. (2025), Optimizing subroutines in assembly language An optimization guide for x86 platforms, available at https://www.agner.org/optimize/optimizing_assembly.pdf
13. Fog, A. (2026), The microarchitecture of Intel, AMD, and VIA CPUs, available at: https://www.agner.org/optimize/microarchitecture.pdf
14. Fog, A. (2025), Instruction tables: Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs, available at: https://www.agner.org/optimize/instruction_tables.pdf
15. Khuong P.-V., and Morin, P. (2017), “Array Layouts for Comparison-Based Searching”, Journal of Experimental Algorithmics, vol. 22, pр. 1–39, doi: https://doi.org/10.1145/3053370 DOI: https://doi.org/10.1145/3053370
16. Shostak, A. (2026), “Comparative experimental analysis of metods for implementing the AVL tree”, Control, Navigation and Communication Systems, no. 1, pp. 131–134, doi: https://doi: 10.26906/SUNZ.2026.1.131 DOI: https://doi.org/10.26906/SUNZ.2026.1.131
17. Anderson, S.E. (2026), Bit Twiddling Hacks, available at: https://graphics.stanford.edu/~seander/bithacks.html
18. Warren H. S. (2013), Hacker’s Delight, Addison-Wesley, 2nd ed., 512 р., available at: https://dl.acm.org/doi/10.5555/2462741
19. (2026), Branchless Programming, available at: https://en.algorithmica.org/hpc/pipelining/branchless/
20. Mowry, T.C., Lam, M. S., and Gupta A. (1992), “Design and Evaluation of a Compiler Algorithm for Prefetching”, Proceedings of ASPLOS-V, pp. 62–73, available at: https://suif.stanford.edu/papers/mowry92.pdf DOI: https://doi.org/10.1145/143371.143488
21. Luk C.-K., and Mowry, T.C. (1996), “Compiler-Based Prefetching for Recursive Data Structures”, Proceedings of ASPLOSVII, pp. 222–233, available at: https://www.cs.tufts.edu/comp/150IPL/papers/luk96prefetch.pdf DOI: https://doi.org/10.1145/248209.237190
Завантаження
Опубліковано
Номер
Розділ
Ліцензія
Авторське право (c) 2026 Anatolii Shostak
Ця робота ліцензується відповідно до ліцензії Creative Commons Attribution-NonCommercial 4.0 International License.
