November 2012
typename Google
Some cache misses
По повод лекцията на Бярне от началото на годината, и едно леко почесване по главата по време на работа преди няколко дни на тема, лоши ли са кеш-мисовете и имат ли те почва у нас, реших днес да проверя от първа ръка 🙂
Ето една проста задачка с интересни резултати 🙂
Имаме масив с N целочислени числа от 0 до N-1, записани в произволен ред.
Искаме да намерите i-тото от тях, да гo изтрием, но да запазим реда им.
Но вместо i-тото, да вземем да изтрием всички от 0 до N-1 и да ги изтрием едно по-едно .. Питаме се каква структура от данни да ползваме, така че това да се случи най-бързо.
Та, обичайните кандидати .. линеен масив и свързан списък. Свързаният списък изглежда по-обещаващ, вместо да копираме всеки път, само ще меним разни поинтъри.
Правим тестове със std::vector, std::list, custom vector && custom list (кода се намира по-долу)
За да е по-къса цялата лудория, имплементирал съм само методите, които са нужни за демонстрацията (няма деструктури и т.н.). Съобщавайте ако има major грешки в коментарите по-долу.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 |
#include <iostream> #include <string> #include <sstream> #include <cstdlib> #include <ctime> #include <vector> #include <list> double diffclock(clock_t clock1,clock_t clock2){ double diffticks = clock1 - clock2; return (diffticks) / CLOCKS_PER_SEC; } template <typename T> class List { public: List():first(nullptr), last(nullptr){} bool empty() const { return first == nullptr; } bool add(T data) { Node* newNode = new Node(data); if (first == nullptr) { last = first = newNode; } else { last->next = newNode; newNode->prev = last; newNode->next = nullptr; last = newNode; } return true; } bool remove(T data) { Node* temp = first; while (temp && temp->data != data) temp = temp->next; if (!temp) return false; if (temp == first) { Node* newFirst = first->next; delete first; if (newFirst) newFirst->prev = nullptr; first = newFirst; } else if (temp == last) { Node* newLast = last->prev; delete last; if (newLast) newLast->next = nullptr; last = newLast; } else { Node* left = temp->prev; Node* right = temp->next; delete temp; left->next = right; right->prev = left; } return true; } private: struct Node { Node(T dataRhs):data(dataRhs), prev(nullptr), next(nullptr){} T data; Node* prev; Node* next; }; Node* first; Node* last; }; template <typename T> class Vector { public: Vector():ptr(nullptr), index(0), maxSize(0){} bool empty() const { return index == 0; } bool reset(int newSize) { delete[] ptr; ptr = new T[newSize]; maxSize = newSize; return true; } bool add(T data) { if (index == maxSize) return false; ptr[index++] = data; return true; } bool remove(T data) { int remIndex = -1; for (int i = 0; i < maxSize; ++i) { if (ptr[i] == data) { remIndex = i; break; }; } if (remIndex == -1) return false; memmove(&ptr[remIndex], &ptr[remIndex + 1], maxSize - remIndex); --index; return true; } private: T* ptr; int index; int maxSize; }; const int SIZE = 81000; template <typename T> void eraseContainer(T& container) { for (int i = 0; i < SIZE; ++i) container.remove(i); } template <typename T> void eraseContainer(std::vector<T>& vec) { for (int i = 0; i < SIZE; ++i) { auto iter = std::find(vec.begin(), vec.end(), i); vec.erase(iter); } } double stdVecTime = 0.0; double stdListTime = 0.0; double customVecTime = 0.0; double customListTime = 0.0; void test() { std::vector<int> vecStd; vecStd.reserve(SIZE); for (int i = 0; i < SIZE; ++i) vecStd.push_back(i); std::random_shuffle(vecStd.begin(), vecStd.end()); using namespace std; std::list<int> listStd; for (int i = 0; i < SIZE; ++i) listStd.push_back(vecStd[i]); Vector<int> vecCustom; vecCustom.reset(SIZE); for (int i = 0; i < SIZE; ++i) vecCustom.add(vecStd[i]); List<int> listCustom; for (int i = 0; i < SIZE; ++i) listCustom.add(vecStd[i]); clock_t beginStdVec = clock(); eraseContainer(vecStd); clock_t endStdVec = clock(); stdVecTime+= double(diffclock(endStdVec,beginStdVec)); if(!vecStd.empty()) printf("Bug in std vector test\n"); clock_t beginStdList = clock(); eraseContainer(listStd); clock_t endStdList = clock(); stdListTime += double(diffclock(endStdList,beginStdList)); if(!listStd.empty()) printf("Bug in std list test\n"); clock_t beginVec = clock(); eraseContainer(vecCustom); clock_t endVec = clock(); customVecTime += double(diffclock(endVec,beginVec)) ; if(!vecCustom.empty()) printf("Bug in custom vector test\n"); clock_t beginList = clock(); eraseContainer(listCustom); clock_t endList = clock(); customListTime += double(diffclock(endList,beginList)); if(!listCustom.empty()) printf("Bug in custom list test\n"); } int main(int argc, const char * argv[]) { const double testTimes = 1.0; srand((unsigned)time(0)); for (int i = 0; i < testTimes; ++i) test(); std::cout << "Std vec time:" << stdVecTime / testTimes << std::endl; std::cout << "Std list time:" << stdListTime / testTimes << std::endl; std::cout << "Custom vec time:" << customVecTime / testTimes << std::endl; std::cout << "Custom list time:" << customListTime / testTimes<< std::endl; return 0; } |
Компилатора е LLVM4.1 с всички оптимизации, процесора – Core2Duo 2.26ghz (P8400), MacOS 10.8.1. Структурите custom vec && custom list всъщност не са от значение, тъй като най-често ни интересуват резултатите от std (написах ги от носталгия, след като завърших хората спряха да ме карат да ги пиша непрекъснато)
Ето и резултатите (lower is better). Замерванията са правени по 3 пъти, показано е средно аритметичното:
По всичко личи, че моя вектор не е много бърз. Това е добре, имплементацията не изглежда много грешна, но пък е бавна. +1 за STL-a 🙂
И понеже никой не харесва таблици, ето ги в арт вариант :
И понеже не се виждат тези в началото заради скалирането, ето ги и тях :
Не ми се мисли, разни езици от високо ниво, пазещи програмистите от “странични ефекти на кода {}”, ползващи за пестене на памет разни линкчета насам-натам колко бързо работят 🙂
Изглежда че vector е the silver bullet (и не е вярно, че ако има честа нужда от махане на елементи в средата list-a върши работата екстра), а и че за тези неща трябва да се говори в университета, че срамота така завършваме неуки …