Some cache misses

По повод лекцията на Бярне от началото на годината, и едно леко почесване по главата по време на работа преди няколко дни на тема, лоши ли са кеш-мисовете и имат ли те почва у нас, реших днес да проверя от първа ръка 🙂

Ето една проста задачка с интересни резултати 🙂

Имаме масив с N целочислени числа от 0 до N-1, записани в произволен ред.

Искаме да намерите i-тото от тях, да гo изтрием, но да запазим реда им.
Но вместо i-тото, да вземем да изтрием всички от 0 до N-1 и да ги изтрием едно по-едно .. Питаме се каква структура от данни да ползваме, така че това да се случи най-бързо.

Та, обичайните кандидати .. линеен масив и свързан списък. Свързаният списък изглежда по-обещаващ, вместо да копираме всеки път, само ще меним разни поинтъри.

Правим тестове със std::vector, std::list, custom vector && custom list (кода се намира по-долу)
За да е по-къса цялата лудория, имплементирал съм само методите, които са нужни за демонстрацията (няма деструктури и т.н.). Съобщавайте ако има major грешки в коментарите по-долу.

Компилатора е 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 върши работата екстра), а и че за тези неща трябва да се говори в университета, че срамота така завършваме неуки …