tag:blogger.com,1999:blog-410416665291724878.post4767848735157956733..comments2022-12-19T13:52:22.907+04:00Comments on >рабочие заметки: Simple concurrent cachesRuslan Chereminhttp://www.blogger.com/profile/01023948540752159657noreply@blogger.comBlogger22125tag:blogger.com,1999:blog-410416665291724878.post-60221076925125563252012-06-29T12:01:49.742+04:002012-06-29T12:01:49.742+04:00@ivan
Про weakCAS я уже писал несколько раз. Как ...@ivan <br />Про weakCAS я уже писал несколько раз. Как и про lazySet, из той же оперы -- совсем недавно. На x86 weakCAS == CAS, там нет атомиков без барьера. Такие штуки есть на ARM (вроде бы) и на Azul VEGA (точно), для них это актуально.<br /><br />Про объем неконсистентности: надо все-таки отделять мух от котлет. JMM это инструмент доказательства формальной корректности. Это не инструмент Ruslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-82504528188901070462012-06-28T13:59:46.791+04:002012-06-28T13:59:46.791+04:00>> "Общий объем неконсистентности на си...>> "Общий объем неконсистентности на системах с hcc будет не больше, чем (размер регистров)*(число потоков), а в реальности гораздо меньше, потому что сложно иметь осмысленный код, который сколько-либо заметное время держит какие-то данные в регистрах."<br /><br />Если бы мы писали на ассемблере, то однозначно бы с тобой согласился. Но в JVM Spec 3(java 5) были понятия "Golovach Ivanhttps://www.blogger.com/profile/17934541017925930523noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-10408403359257633012012-06-28T13:22:13.268+04:002012-06-28T13:22:13.268+04:00А что ты думаешь на счет AtomicReferenceArray.weak...А что ты думаешь на счет AtomicReferenceArray.weakCompareAndSet(...)[http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/atomic/AtomicReferenceArray.html#weakCompareAndSet(int, E, E)]?<br />- есть гарантии, что обновление пройдет<br />- нет платы за синхронизацию = "weakCompareAndSet atomically reads and conditionally writes a variable, is ordered with respect to other memory Golovach Ivanhttps://www.blogger.com/profile/17934541017925930523noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-31283030934251019572012-06-27T20:20:48.248+04:002012-06-27T20:20:48.248+04:00Я спрашивал Джереми на счет его "эмулятора JM...Я спрашивал Джереми на счет его "эмулятора JMM" - он ответил, что никому не дает, так как он неверно работает:). Раз один из авторов допускает ошибки при попытке реализации эмулятора, значит commitment protocol, фактически, полное Г.<br />Вот второй пример на котором я застрял:<br /><br />Изначально x==0;<br /><br />Поток #0:<br />x = 1;<br />println("#0: " + x);<br /><br />Golovach Ivanhttps://www.blogger.com/profile/17934541017925930523noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-44283463095797609952012-06-27T20:09:01.719+04:002012-06-27T20:09:01.719+04:00На протоколе подтверждения я тоже пока завис :)
...На протоколе подтверждения я тоже пока завис :) <br /><br />Насколько я сейчас думаю -- нет, то, что вы описали невозможно по JMM. Потому что какая-то запись либо подтверждена, либо нет -- и если уж чтение увидело результат какой-то записи, то она-таки уже не может быть "отменена", и перепременена позже. Но это лишь мое мнениеRuslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-26181583105706884802012-06-27T20:05:44.117+04:002012-06-27T20:05:44.117+04:00Продолжая "буквоедство":
На счет eventua...Продолжая "буквоедство":<br />На счет eventually consistency есть более интересный момент. EC неявно предполагает "однонаправленность времени": скажем обновления с одной ноды/потока/агента/актора сохраняют порядок (PRAM/FIFO consistency/Processor consistency: http://en.wikipedia.org/wiki/PRAM_consistency). <br /> С hb-ребрами я разобрался, но на commitment protocol от Golovach Ivanhttps://www.blogger.com/profile/17934541017925930523noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-8741766386724437062012-06-27T20:05:28.723+04:002012-06-27T20:05:28.723+04:00@ivan
>String.hashCode().
Да, разумеется, каж...@ivan<br />>String.hashCode(). <br /><br />Да, разумеется, кажется даже, я именно им и вдохновлялся. И меня удивляет-то именно то, что дальше hashCode почему-то никто не идет. Собственно, immutable объекты в джаве имеют в некотором смысле семантику примитивов -- как int не может быть записан "наполовину", так и ссылка на immutable объект не может быть передана на "наполовину&Ruslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-70758072370252036852012-06-27T19:38:12.435+04:002012-06-27T19:38:12.435+04:00>> "Когда-нибудь -- понятие растяжимое ...>> "Когда-нибудь -- понятие растяжимое :) Можит, и никогда."<br /> Ну ... Если быть уж совсем "буквоедом", то<br />- Wiki [http://en.wikipedia.org/wiki/Eventual_consistency]: "It means that given a sufficiently long period of time over which no changes are sent, all updates can be expected to propagate eventually through the system and all the replicas will be Golovach Ivanhttps://www.blogger.com/profile/17934541017925930523noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-26538277410572237932012-06-27T19:29:28.864+04:002012-06-27T19:29:28.864+04:00>> "data race based конкурентного кэша ...>> "data race based конкурентного кэша без какой-либо синхронизации. ... за прошедший год я так нигде и не встретил ничего подобного".<br /> Кэша я тоже не видел, но в целом, эта идея использована авторами Sun JDK в String.hashCode(). Значение кэшируется в non-volatile переменной. Так как значение int, то их пример работает и в старой JMM (им не требуется новая семантика для Golovach Ivanhttps://www.blogger.com/profile/17934541017925930523noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-3537729568625666942012-06-25T10:40:54.539+04:002012-06-25T10:40:54.539+04:00@elizarov
>При таком алгоритме двойного хеширо...@elizarov <br />>При таком алгоритме двойного хеширования надо увеличивать индекс на второй хеш, а не уменьшать. Это важно. Догадайтесь сами почему.<br /><br />Не догадался, расскажите. Есть пара гипотез, но на "важно" они никак не тянут. Бенчмарки тоже не показывают сколь-либо заметного эффектаRuslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-14934280842039465272012-06-22T14:30:35.225+04:002012-06-22T14:30:35.225+04:00Да, должен. Нет, код этого не гарантирует. Размер ...Да, должен. Нет, код этого не гарантирует. Размер лучше выбирать простым числом, тогда все будет круто. Но и для обычных чисел все скорее всего будет неплохо -- потому что число проб больше 3-4 это уже признак плохо выбранного размера, или плохой хэш-функции.Ruslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-77149409395292595232012-06-22T14:05:45.816+04:002012-06-22T14:05:45.816+04:00А разве probe не должен оказаться взаимно-простым ...А разве probe не должен оказаться взаимно-простым с length? Кажется, код этого не гарантирует.MikeMirzayanovhttps://www.blogger.com/profile/05666744249015308576noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-81111111538338413852012-06-19T08:30:47.148+04:002012-06-19T08:30:47.148+04:00@gvsmirnov Когда-нибудь -- понятие растяжимое :) М...@gvsmirnov Когда-нибудь -- понятие растяжимое :) Можит, и никогда.<br /><br />Нет, из JMM гарантии прогресса (в смысле -- сходимости всех видимых образов кэша к одному) не выводятся. Есть несложные примеры кода, которые почти наверняка и в реальности дадут несходимость. Поток с бесконечным циклом с коротким телом, где идет вызов кэша с фиксированным ключом, например.<br /><br />Другое дело, что сRuslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-17251386859600640002012-06-19T01:26:08.200+04:002012-06-19T01:26:08.200+04:00@cheremin Прямо так уже eventually consistent? Я п...@cheremin Прямо так уже eventually consistent? Я понимаю, что на практике на уровне железа кеши eventually consistent, но на уровне Java же нет? Или из JMM следует? Если да, то я не понимаю, как.gvsmirnovhttps://www.blogger.com/profile/09213176675225121755noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-64576570555312338362012-06-18T18:43:27.856+04:002012-06-18T18:43:27.856+04:00@gvsmirnov Не, отдельно на purge акцентировать не ...@gvsmirnov Не, отдельно на purge акцентировать не нужно -- нужно акцентировать на том, что весь кэш evantually consistent.Ruslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-53264241039197943772012-06-18T15:37:40.530+04:002012-06-18T15:37:40.530+04:00Руслан, ну как обычно. При прочих равных дали тест...Руслан, ну как обычно. При прочих равных дали тестовую нагрузку, померили целевых попугаев. В данном случае, полагаю, пытались уменьшить latency для транзакций. Прошлую статью проглядел. Бенчмарки посмотрел, спасибо :)<br /><br />Кстати, имо, нужно отдельно акцентировать внимание на контракте purge: несколько контринтуитивно, что после его вызова другие потоки ещё могут увидеть старые значения.<gvsmirnovhttps://www.blogger.com/profile/09213176675225121755noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-7076264491131902012012-06-18T14:10:51.076+04:002012-06-18T14:10:51.076+04:00@elizarov
как бы не очевидно, почему надо инкреме...@elizarov<br /><br />как бы не очевидно, почему надо инкрементировать, а не декрементировать. собственно cache калька с trove, который как показывают <a href="http://elizarov.livejournal.com/25221.html" rel="nofollow">ваши же тесты в статье Пишем самый быстрый хеш для кэширования данных: Часть 1</a> самый быстрый.<br /><br />Напришивается вопрос - где нестыковка ?Vladimir Dolzhenkohttps://www.blogger.com/profile/09353866985268525403noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-7182192651997796892012-06-18T00:54:31.402+04:002012-06-18T00:54:31.402+04:00При таком алгоритме двойного хеширования надо уве...При таком алгоритме двойного хеширования надо увеличивать индекс на второй хеш, а не уменьшать. Это важно. Догадайтесь сами почему.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-10276344852738317482012-06-17T23:59:31.404+04:002012-06-17T23:59:31.404+04:00После "currency" внезапно захотелось про...После "currency" внезапно захотелось проверить, где вы работаете :)Nikolay Bukharevhttps://www.blogger.com/profile/00411486919562028301noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-67420331241655845762012-06-17T23:43:18.455+04:002012-06-17T23:43:18.455+04:00@gvsmirnov
разогрев lazy cache происходит задолго...@gvsmirnov<br /><br />разогрев lazy cache происходит задолго до торговли, так, что замарачиваться не стоит)Vladimir Dolzhenkohttps://www.blogger.com/profile/09353866985268525403noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-54869236090353535032012-06-17T20:53:31.263+04:002012-06-17T20:53:31.263+04:00Все стало быстрее over 9000 раз -- разве не очевид...Все стало быстрее over 9000 раз -- разве не очевидно?<br /><br />Как ты будешь измерять эффект в большом приложении? Там слишком много факторов. Мне кажется, что быстрее, чем здесь -- просто сделать нельзя. Конкурентный кэш по цене однопоточного -- чего тебе еще ;)<br /><br />Микробенчмарки годичной давности показывали стоимость .get() в 2-2.5 раза меньше, чем ComputableConcurrentHashMap из guavaRuslan Chereminhttps://www.blogger.com/profile/01023948540752159657noreply@blogger.comtag:blogger.com,1999:blog-410416665291724878.post-90929341715462517492012-06-17T20:13:54.395+04:002012-06-17T20:13:54.395+04:00А где циферки? Интересно же, как в конкретном прил...А где циферки? Интересно же, как в конкретном приложении это помогло.<br /><br />Кстати, в случае фондовых бирж большинство адекватных торговых площадок позволяют получить список торгующихся в данной сессии инструментов. Думаю, для валютных бирж ситуация аналогична. Можно их заранее получить, и запопулировать кеш предварительно, сэкономив на первом получении во время торговой сессии.<br /><br />gvsmirnovhttps://www.blogger.com/profile/09213176675225121755noreply@blogger.com