1. C++ / Говнокод #27421

    0

    1. 1
    2. 2
    3. 3
    Нужно реализовать thread-safe set.
На сколько нормально разбить сет на N бакетов (по хешу, условно, 10000 штук),
тогда при добавлении или удалении элемента делать лок соответствующего бакета

    Но будет хуево, когда пойдут запросы по одному ключу в нескольких тредах.
    Есть решение лучше?

    Запостил: 3_dar, 12 Мая 2021

    Комментарии (9) RSS

    • ava bormand 12.05.2021 15:04 # +3

      > по одному ключу в нескольких тредах

      Ну это уже неизлечимая проблема, как мне кажется, если они реально к одному ключу лезут... По крайней мере большую часть пересечений ты таким разбиением убрал.

      З.Ы. В джаве вроде такая реализация и есть.
      Ответить

      • ava booratihno 12.05.2021 15:20 # 0

        можно сделать в каждом треде свой кеш, и обновлять его когда обнавляется значение

        если ты пишешь раз в год, а читаешь раз в ms, то будет хорошо
        Ответить

        • ava bormand 12.05.2021 15:24 # +1

          > если ты пишешь раз в год...

          ... то можно вообще не париться и юзать иммутабельные структуры. Один атомик на чтение корня и дальше вообще насрать на конкуренцию.
          Ответить

    • ava PolinaAksenova 12.05.2021 15:11 # +3

      Делай ня lock-free деревьях, будь девочкой-волшебняцей!
      https://github.com/zhangshun97/Lock-free-Red-black-tree
      Ответить

      • ava CHayT 12.05.2021 16:27 # +1

        Был в сети анализ количества поправок в статьи по lock-free структурам данных, и из него следовало, что даже учёные - в воде мочёные постоянно обсираются в своём псевдокоде.
        Ответить

        • ava j123123 12.05.2021 21:10 # +1

          Надо было формально доказывать свои lock-free структуры, чтоб не обсираться.
          Ответить

        • ava bormand 13.05.2021 08:29 # 0

          > поправок в статьи

          Ага, там по-моему 99% статей про локфри в духе "они вот тут обосрались, но мы пофиксим это вот так"...

          Я даже не знаю, в итоге есть какая-нибудь формально корректная реализация?
          Ответить

    • ava guest6 12.05.2021 15:14 # +2

      а ты будешь чаще писать или читать?

      позырь тут
      https://www.baeldung.com/lock-free-programming


      https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html
      Ответить

    Добавить комментарий