Потокобезопасный кэш

[Igors]

Итак, пусть pageData() вызван одновременно из 3-х потоков для разных страниц. В последнем (третьем) вызове из кэша будут удалены самые первые данные, т.е. данные, которые в настоящий момент активно юзает первый поток. Счетчик ссылок для этих данных упадет до 1, и когда первый поток их обработает, память освободится.

Так-то оно так, но при этом в памяти могут быть 2 и более копии одной страницы, используемые разными нитками. Поэтому будет работать корректно для "только чтение".

Кроме того, досадно что при любом обращении к кэшу нитки "сталкиваются лбами" на входном мутексе, и при интенсивном обращении к кэшу это ощутимо.

Не совсем.

Точно, но давайте другим поясним почему: код ниже не "потокобезопасен" и рухнет на 2 и более нитках

Код:

 if (mData.isNull())    // страница не загружена?
                               <---- Пробой здесь 
  mData = TSharedPtr(LoadPage());  // загружаем ее, счетчик = 1

[brankovic]

Так-то оно так, но при этом в памяти могут быть 2 и более копии одной страницы, используемые разными нитками. Поэтому будет работать корректно для "только чтение".

Кроме того, досадно что при любом обращении к кэшу нитки "сталкиваются лбами" на входном мутексе, и при интенсивном обращении к кэшу это ощутимо.

А вы разделите кэш на 8 частей, к каждой свой мьютекс:

struct cache_part
{
   cache c;
   mutex m;
} parts [8];

а при обращении берите % 8, и сталкиваться будут в 8 раз реже.

[Igors]

А вы разделите кэш на 8 частей, к каждой свой мьютекс:

struct cache_part
{
   cache c;
   mutex m;
} parts [8];

а при обращении берите % 8, и сталкиваться будут в 8 раз реже.

Прием хороший, но и емкость кэша уменьшится в 8 раз  Так что вполне возможно один кэш будет крутиться как белка в колесе выгружать/подгружать, а остальные будут стоять. Ну и это я просто так сказал, мол, одно большое изображение - для простоты. В действительности их может быть любое кол-во (разные данные хранятся в страницах и подкачиваются) и вычислять "какой кэш" придется для каждого типа.

Понимаю что задача сложная и "идеального" решения, может быть, и не существует. Мне не нравится что "сразу захватили мутекс" (хотя Qt так всегда делает). Ведь частота попаданий в кэш, как правило, 80% и больше. Часто даже 100% (ну хватило памяти). Вот как бы оптимизировать "просто чтение", напр

- обращаемся к странице, атомарно увеличили ее счетчик
- если счетчик > 0, просто пользуем страницу, закончили - уменьшили счетчик
- а вот иначе (счетчик < 0) - тогда уже берем локи, это случай редкий, можно и потерпеть   

[twp]

может в данной задаче лучше применить файл, проецируемый в память?

[Igors]

может в данной задаче лучше применить файл, проецируемый в память?

Конкретно файл не пробовал, а вот выделять больше памяти чем есть физически - проверялось не раз. Результаты: оба ОС на которых я работаю  (OSX и WinXP64) хотя и не ложатся, но проигрывают скромной "ручной" подкачке с разгромным счетом - если "только" в 5 раз медленнее - то еще и хорошо 

Ну и пока есть 32-bit пользователи - это решение не общее.

[brankovic]

емкость кэша уменьшится в 8 раз 

не изменится никак (или не понимаю, что вы называете ёмкостью)

Так что вполне возможно один кэш будет крутиться как белка в колесе выгружать/подгружать, а остальные будут стоять.

Так ведь и в hash_map все хэши могут совпасть, но люди же пользуются. Там вопрос в аккуратном выборе хэша, здесь -- в равномерном распределении по 8-и кэшам.

(разные данные хранятся в страницах и подкачиваются) и вычислять "какой кэш" придется для каждого типа.

конечно, а в хэш мэпе надо хэш вычислять для каждого элемента, при каждом обращении.

Мне не нравится что "сразу захватили мутекс"

если успели отработать до следующего клиента, то ничего страшного. Хотя зависит от системы, если mutex::lock выходит в режим ядра, то это дороговато.

Вот как бы оптимизировать "просто чтение"
- обращаемся к странице, атомарно увеличили ее счетчик
- если счетчик > 0, просто пользуем страницу, закончили - уменьшили счетчик
- а вот иначе (счетчик < 0) - тогда уже берем локи, это случай редкий, можно и потерпеть   

непонятно.. Правильно я догадываюсь, что вы хотите такой shared_ptr, который бы не падал в PageHeader::GetData?

[twp]

может в данной задаче лучше применить файл, проецируемый в память?

Конкретно файл не пробовал, а вот выделять больше памяти чем есть физически - проверялось не раз. Результаты: оба ОС на которых я работаю  (OSX и WinXP64) хотя и не ложатся, но проигрывают скромной "ручной" подкачке с разгромным счетом - если "только" в 5 раз медленнее - то еще и хорошо 

Ну и пока есть 32-bit пользователи - это решение не общее.

Но я так понял загружать весь файл не нужно? Ведь при маппинге можно указать нужный кусок памяти.

[Igors]

Но я так понял загружать весь файл не нужно? Ведь при маппинге можно указать нужный кусок памяти.

Вариант "просто дать больше памяти" выглядит равнозначным. Все то же самое, просто "кэш достаточно велик чтобы вместить все" - никогда не происходит вытеснения. Результаты печально медленны 

[Igors]

Давайте я сначала отвечу на первое

емкость кэша уменьшится в 8 раз 

не изменится никак (или не понимаю, что вы называете ёмкостью)

Емкость кзша - это число страниц которые могут быть в памяти. Если емкость превышена, наименее используемая страница должна быть выгружена чтобы освободить место. Если хотим иметь напр 8 кэшей, простейшее решение поделить емкость на 8. Можем конечно не делить, но тогда нам придется отслеживать чтобы общее число загруженных страниц не превысило заданное - и это надо защищать глобальной блокировкой. Кроме того, каждый кэш может вытеснять только "свои" страницы. И что делать если у кэша НЕТ загруженных станиц, но их общее число превысило предел (др кэши загрузили) ? Кого вытеснять?    А даже если и есть кого, заметим: это будет страница наименее пользуемая "в данном кэше", значит число подкачек растет.

В общем "чем красивше выглядит решение - тем сложнее его реализовать" 

[Igors]

(разные данные хранятся в страницах и подкачиваются) и вычислять "какой кэш" придется для каждого типа.

конечно, а в хэш мэпе надо хэш вычислять для каждого элемента, при каждом обращении.

Если все заголовки страниц держать в памяти - то почему бы просто не вписать в каждый заголовок номер кэша? Так что, может быть, насчет переделок структур данных я был неправ 

непонятно.. Правильно я догадываюсь, что вы хотите такой shared_ptr, который бы не падал в PageHeader::GetData?

Я хочу чтобы наиболее популярная операция - чтение уже загруженной страницы - проходила "сквозняком" на атомарных операциях со счетчиком этой страницы.

...mutex::lock выходит в режим ядра, то это дороговато.

"дороговато" - то очень мягко сказано. При интенсивной конкуренции мутекс убивает скорость в ноль.

[twp]

(разные данные хранятся в страницах и подкачиваются) и вычислять "какой кэш" придется для каждого типа.

конечно, а в хэш мэпе надо хэш вычислять для каждого элемента, при каждом обращении.

Если все заголовки страниц держать в памяти - то почему бы просто не вписать в каждый заголовок номер кэша? Так что, может быть, насчет переделок структур данных я был неправ 

непонятно.. Правильно я догадываюсь, что вы хотите такой shared_ptr, который бы не падал в PageHeader::GetData?

Я хочу чтобы наиболее популярная операция - чтение уже загруженной страницы - проходила "сквозняком" на атомарных операциях со счетчиком этой страницы.

...mutex::lock выходит в режим ядра, то это дороговато.

"дороговато" - то очень мягко сказано. При интенсивной конкуренции мутекс убивает скорость в ноль.

QReadLocker не оно? или просто использовать несколько QSharedMemory

[brankovic]

Если емкость превышена, наименее используемая страница должна быть выгружена чтобы освободить место. Если хотим иметь напр 8 кэшей, простейшее решение поделить емкость на 8. Можем конечно не делить, но тогда нам придется отслеживать чтобы общее число загруженных страниц не превысило заданное - и это надо защищать глобальной блокировкой.

Да, это я проглядел. Но проблема непринципиальная. Можно обойтись и без 9-го мьютекса, только атомарными операциями. Можно с 9-м мьютексом. Можно и на восемь ёмкость разделить в конце концов.

Не очевидно, что из этого быстрее и быстрее ли вообще -- надо проверять на живом примере. Подобная оптимизация (разбиение кэша на 8 частей) эффективна, если  толкание на мьютексах значительное. Проблема в том, что толкание очень трудно померить. По крайней мере я не знаю способа (хотя задача возникала), буду признателен, если что-то предложите.

Я хочу чтобы наиболее популярная операция - чтение уже загруженной страницы - проходила "сквозняком" на атомарных операциях со счетчиком этой страницы.

"Чтение" у вас, как я понял, это
1 поиск в кэше
2 копирование shared_ptr <Page>
3 сохранение отметки о недавнем использовании этой страницы

то есть даже в чтении присутствует пара записей, а ведь есть же ещё ветка, когда страница не найдётся. Слишком сложные операции, простого lockfree решения тут нет.

...mutex::lock выходит в режим ядра, то это дороговато.

"дороговато" - то очень мягко сказано. При интенсивной конкуренции мутекс убивает скорость в ноль.

Я не о конкуренции, я о замедлении, которое даёт вызов lock для незалоченного мьютекса. В виндовой реализации QMutex, нагорожен целый огород, только чтобы в режим ядра не попасть. В результате на пару lock/unlock приходится 1 системный вызов если всё хорошо, и 2, если мьютекс таки был занят.

К чему это всё. Если у вас программа работает со страницами, то полезная работа обычно занимает на порядки больше времени, чем поиск в кэше. Поэтому реального толкания не возникает: тред захватывает мьютекс, мухой ищет в кэше, отдаёт мьютекс и идёт делать 99% работы. Очень редко, условно в 1% случаев он засыпает посреди чтения мьютекса, или треды случайно сталкиваются. Но эту заминку надо умножать 1%, поскольку в 99% случаев её просто нет.

Неприятно бывает, когда тред захватывает мьютекс, и начинает делать что-то долгое, например грузить с диска (так было в решении от Akon). Вот эту ситуацию легко оптимизировать: снять лок кэша, загрузить страницу, залочить кэш снова, положить в него загруженную страницу, разлочить кэш, продолжить работу с загруженной страницей.

В общем я за решение от Akon, с поправкой на прошлый абзац.

[brankovic]

QReadLocker не оно?

Вообще-то именно трений среди читающих Igors и хотел избежать. Совсем в чистом виде использовать нельзя -- каждый читающий хочет оставить метку о недавнем использовании страницы, а это запись. Но можно ввести доп. мьютекс. Тут надо пробовать и замерять время, теоретически может быть выигрыш.

или просто использовать несколько QSharedMemory

или сразу особую уличную магию!

[twp]

QReadLocker не оно?

Вообще-то именно трений среди читающих Igors и хотел избежать. Совсем в чистом виде использовать нельзя -- каждый читающий хочет оставить метку о недавнем использовании страницы, а это запись. Но можно ввести доп. мьютекс. Тут надо пробовать и замерять время, теоретически может быть выигрыш.

или просто использовать несколько QSharedMemory

или сразу особую уличную магию!

зачем мютекс для такой мелочи? QAtomicInt достатотчно

[Igors]

зачем мютекс для такой мелочи? QAtomicInt достатотчно

Так и хочу - но тогда не получается использовать готовые классы (QReadWriteLock и др). Не беда, все равно от них здесь толку мало