Giter Club home page Giter Club logo

cache-effective-binary-tree's Introduction

Домашнее задание №2 по курсу «Архитектура Компьютеров»

Разработать эффективные а) представление и б) реализации операций вставки, удаления и поиска для двоичных деревьев;

Домашнее задание №2, также как №1, подразумевало исследовательскую составляющую.

Результаты

В данной работе было разработано кэш-эффективное представление двоичных НЕ сбалансированных деревьев (для сбалансированных смотрите btree). Для этого дерево было разбито на кластеры, которые содержат по C вершин. Вершины внутри кластера выкладывались внутри массива с помощью различных "укладок" BFS/vEB/DFS/INORDER. В результате тестов было выяснено, что порядок vEB позволяет достичь наибольшей скорости для операций вставка/поиск, а размер кластера оптимально брать 63. (см отчёт.pdf)

Операция удаления реализована не была.

Компиляция

Код написан на языке С, для компиляции выполнить:

  • qmake Arch2_b.pro
  • make

Управляющие директивы препроцессора

В файле "include.h"

  1. Если объявлено
#define USE_CACHE_TEST

То выполняется тестирование "кэш-эффективной" версии, иначе обычной версии бинарных деревьев

  1. Если объявлено
#define USE_CLUSTER_SORT

То при вставке в "кэш-эффективной" версии появляется перебалансировка внутри кластера.

#define CACHE_LINE_SIZE 64 

Задает размер кэш-линии (используется в malloc для выравнивания).

#define C_SIZE ((1 << 5)-1) 

Задает размер кластера. Должна быть степенью двойки >= 4 (то что тестировалось).

//#define USE_BFS
#define USE_VEB
//#define USE_DFS
//#define USE_INORDER

Задает используему укладку кластера.

#define USE_ALLOCATOR

Использование самописного простого аллокатора памяти. Иначе используется malloc.

Запуск

Приложение является консольным, первым параметром принимает путь к файлу с тестами на вставку. Вторым параметром путь к файлу с тестами на поиск. Выводит время, которое потребовалось на выполнение всех операций вставки и поиска.

Формат файла с тестами:

  1. В первой строке 64 разрядное беззнаковое число количество пар ключ-значение
  2. Во второй и последующий 64 разрядные беззнаковые пары чисел "ключ значение"

Пример входного теста:

2
1 2
3 4

Пример результата работы программы:

Used layout: vEB
C_SIZE: 31
KEYS_SIZE: 15
NEXT_SIZE: 16
EXIST_SIZE: 4
CACHE_MISS on exist = 1
Loading data...
Test: insert cache_tree
time elapsed: 1.66600000000000023e-06
Loading data...
Test: search cache_tree
time elapsed: 1.13400000000000007e-06
No-cache tree alloced memory:  0 GB   3 Mb   0 Kb 880 B
Cache-tree alloced memory:     0 GB  24 Mb   0 Kb 960 B

cache-effective-binary-tree's People

Contributors

sargarass avatar

Watchers

 avatar  avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.