Comments 8
Неплохо было бы рассказать об CART, а не только кинуть ссылку на документацию.
Ну это не совсем документация — это публикация, связанная с этим алгоритмом. И, конечно, если уже расписывать CART, то нужно описать все доступные схемы кеширования, их достоинства и недостатки. Это уже больше теоретическая задача, на которую хотелось бы выделить время, имплементировать все схемы и сравнить их.
В данном же случае я ставил за цель имплементировать многопоточную схему, а уже получившимся кодом решил поделиться с остальными разработчиками. С этим связан достаточно куцый обзор самой схемы. Хотя стоит отметить, что исходная публикация сама по себе весьма интересна и описывает определенный бекграунд для интересующихся темой кеширования. Возможно стоит сделать ее перевод?
В данном же случае я ставил за цель имплементировать многопоточную схему, а уже получившимся кодом решил поделиться с остальными разработчиками. С этим связан достаточно куцый обзор самой схемы. Хотя стоит отметить, что исходная публикация сама по себе весьма интересна и описывает определенный бекграунд для интересующихся темой кеширования. Возможно стоит сделать ее перевод?
Лично мне в этой статье не хватило малого — описания принципа работы данного алгоритма. Хотя бы в общих чертах.
Если в общих чертах, то это развитие параллельной LRU ветки алгоритмов кеширования под названием CLOCK. Проблема LRU заключается в том, что необходимо постоянно поддерживать актуальный список элементов кеша в тот момент, когда к ним обращаются. Т.е. обратившись к элементу вы переносите его в конец очереди. Это требует локов и плохо масштабируется при большом количестве потоков.
CLOCK решает эту проблему очень элегантно — он просто идет по кругу (как в часах) всех элементов кеша и выгружает те, у которых не установлен флаг 'long'. Если же флаг установлен, то он его просто сбрасывает и оставляет элемент в кеше. При повторном обращении к элементу вам нужно только установить этот флаг. Схема проста и весьма эффективна.
Проблемы начинаются когда сканируется вся база за кешем (тогда даже часто используемые элементы рискуют быть выгруженными из-за множества проходов «по кругу»), и когда к одному элементу обращаются дважды (ему устанавливается флаг и он проживет минимум два прохода по кругу).
CAR решает эту проблему таким же образом, каким это делает схема ARC — он имеет не один, а два круга. И элементы из первого круга попадают во второй только если они действительно очень популярны. Таким образом решается проблема двойного доступа и сканирования базы.
CART отличается от CAR тем, что держит еще и «историю» последних выгруженных элементов, на основании которой он решает в какой из кругов помещать новый элемент.
CLOCK решает эту проблему очень элегантно — он просто идет по кругу (как в часах) всех элементов кеша и выгружает те, у которых не установлен флаг 'long'. Если же флаг установлен, то он его просто сбрасывает и оставляет элемент в кеше. При повторном обращении к элементу вам нужно только установить этот флаг. Схема проста и весьма эффективна.
Проблемы начинаются когда сканируется вся база за кешем (тогда даже часто используемые элементы рискуют быть выгруженными из-за множества проходов «по кругу»), и когда к одному элементу обращаются дважды (ему устанавливается флаг и он проживет минимум два прохода по кругу).
CAR решает эту проблему таким же образом, каким это делает схема ARC — он имеет не один, а два круга. И элементы из первого круга попадают во второй только если они действительно очень популярны. Таким образом решается проблема двойного доступа и сканирования базы.
CART отличается от CAR тем, что держит еще и «историю» последних выгруженных элементов, на основании которой он решает в какой из кругов помещать новый элемент.
* Простите, промахнулся комментом, мой ответ сверху.
А TBB есть в репозиториях на линухе, или руками приходится ставить?
Да, нужно качнуть с threadingbuildingblocks.org.
Здравствуйте,
Не хотите при помощи этого кода сделать вклад в библиотеку Intel TBB?
Вот ссылка где можно передать патчи, исходный код, бенчмарки и проч.
--Владимир
Не хотите при помощи этого кода сделать вклад в библиотеку Intel TBB?
Вот ссылка где можно передать патчи, исходный код, бенчмарки и проч.
--Владимир
Sign up to leave a comment.
Многопоточная реализация алгоритма кеширования CART