Алгоритм — возможно ли реализовать карту без блокировки в Stack Overflow
Мы разрабатываем C / S на основе сетевых приложений и обнаруживаем, что слишком много блокировок, добавляющих к std :: map, снижает производительность сервера.
Интересно, можно ли реализовать карту без блокировки, если да, то как? Есть ли там открытый исходный код?
РЕДАКТИРОВАТЬ:
На самом деле мы используем std :: map для хранения информации о сокетах, мы сделали инкапсуляцию на основе описания файла сокета, чтобы включить некоторую другую необходимую информацию, такую как IP-адрес, порт, тип сокета, tcp или udp и т. Д.
Подводя итог, мы имеем глобальную карту
map<int fileDescriptor, socketInfor*> SocketsMap,
тогда каждому потоку, который используется для отправки данных, требуется доступ к SocketsMap, и они должны добавить мьютекс перед чтением из SocketsMap или записью в SocketsMap, таким образом, уровень параллелизма всего приложения будет значительно уменьшен из-за большого количества блокировок, добавляемых в SocketsMap.
Чтобы избежать проблемы уровня параллелизма, у нас есть два решения: 1. хранить каждый socketInfor * отдельно 2. использовать какую-то карту без блокировки.
Я хотел бы найти какую-то карту без блокировки, потому что изменения кода, требуемые этим решением, намного меньше, чем в решении 1.
Решение
На самом деле есть способ, хотя я сам не реализовал его, есть документ на заблокировать бесплатную карту с помощью указателей опасности от именитого эксперта по С ++ Андрея Александреску.
Другие решения
Да, я реализовал Неупорядоченная карта без блокировки (документы) в C ++ с использованием концепции «Split-Ordered Lists». Это автоматически расширяющийся контейнер, поддерживающий миллионы элементов в 64-битном CAS без проблем с ABA. С точки зрения производительности, это зверь (см. стр. 5). Это было всесторонне протестировано с миллионами случайных операций.
HashMap подойдет? Посмотри на Intel Threading Building Blocks, у них есть интересная параллельная карта. Я не уверен, что он свободен от блокировки, но, надеюсь, вы заинтересованы в хорошей производительности многопоточности, не особенно в свободе блокировки. Также вы можете проверить CityHash Lib
РЕДАКТИРОВАТЬ:
На самом деле хэш-карта TBB не блокируется
Если вы используете C ++ 11, вы можете взглянуть на AtomicHashMap facebook / глупость
Вы можете реализовать карту, используя оптимистичный дизайн или же транзакционная память.
Этот подход особенно эффективен, если вероятность того, что две операции одновременно обращаются к карте и одна из них изменяет ее структуру, относительно невелика — и вам не нужны накладные расходы на блокировку каждый раз.
Однако время от времени — столкновение происходит, и вам придется каким-то образом его приводить (обычно, возвращаясь к последнему стабильному состоянию и повторяя операции).
Если ваше оборудование поддерживает достаточно атомарные операции — это легко сделать с помощью Сравнить и поменять местами (CAS) — где вы изменяете только ссылку (и всякий раз, когда вы меняете карту, вы работаете с копией карты, а не с оригиналом, и устанавливаете ее в качестве основной только при фиксации).
Я удивлен, что никто не упомянул об этом, но Click Cliff реализовал без ожидания hashmap в Java, который я считаю, может быть перенесен на C ++,