in Computing and stuff

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

Write a Comment

Comment


*

  1. Добре си го разписал – с таблички, графики. Има и наченки на анализ :).
    Освен това настрана, е доста интересно – изглежда custom имплементацията на свързания списък се представя доста добре спрямо std-то. Което ме озадачава всъщност – странно ми е как custom имплементация успява да е по-производителна от lib-ската. Според ми си заслужава да се направят още малко тестове, за да видим дали тази аномалия е тенденциална от гледна точка на операциите или да кажем custom-а се представя много добре само за тази или онази операция – като идеи бих ти дал (освен триенето, което си направил), сортировка, обръщане на списък, копиране на списъци и т.н. Ако имаше време, можеш да го направиш и да споделиш резултати :).

    P.S. Даваш ми идеи да го проверя как е това чудо и в Java-та и JS-а

  2. Интересно как се справя std::forward_list (линеен едносвързан списък) от C++11 спрямо std::list и твоят custom list ?