Thread-safe словарь с авто-инкрементируемым значением
От: AutumnLeaf Великобритания  
Дата: 31.01.15 04:31
Оценка:
Дисклеймер: всегда писал на Java и только недавно стал пользоваться C#, так что просьба не обращать внимание на стиль

Для решения одной задачи понадобилось написать такой словарь, который бы было можно использовать из разных потоков и который бы реализовывал вот такой интерфейс

    public interface IIndexer
    {
        IEnumerable<string> Keys { get; }
        int GetIndex(string key);
        int MaxIndex { get; }
    }


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

Если строка запрашивается впервые, то возвращаемый результат равен количеству строк на данный момент находящихся в словаре и автоматически инкрементируется. Нумерация начинается с нуля. "Дырки" в счетчике не допускаются, то есть если в словаре N строк, то набор индексов должен быть таким: 0, 1, 2, ..., N-1

Предполагается, что есть несколько наборов строк (каждый количеством до нескольки сотен), которые будут проиндексированы при старте приложения и в дальнейшем новые строки запрашиваться не будут.

Написал вот такой код, просьба подсказать, если есть более оптимальный вариант:

  Решение
using System.IO;
using System;
using System.Collections.Generic;
using System.Collections.Concurrent;
using System.Threading;

namespace A
{
    public interface IIndexer
    {
        IEnumerable<string> Keys { get; }
        int GetIndex(string key);
        int MaxIndex { get; }
    }
    
    public class Indexer : IIndexer
    {
        private readonly ConcurrentDictionary<string, Record> _map =
            new ConcurrentDictionary<string, Record>();
            
        private int _counter = -1;
        
        public int GetIndex(string key)
        {
            return _map.GetOrAdd(key, k => new Record(this)).Index;
        }
        
        public int MaxIndex { get { return _counter; } }
        
        public static void Main()
        {
            var indexer = new Indexer();
            char[] alpha = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".ToCharArray();
            Action action = () => 
            {
                foreach (var c in alpha)
                {
                    Console.WriteLine(indexer.GetIndex(c.ToString()));
                    Thread.Yield();
                }
            };
            
            var t1 = new Thread(() => action());
            var t2 = new Thread(() => action());
            var t3 = new Thread(() => action());
            var t4 = new Thread(() => action());
            
            t1.Start();
            t2.Start();
            t3.Start();
            t4.Start();
            
            t1.Join();
            t2.Join();
            t3.Join();
            t4.Join();
            
            var keys = new List<string>(indexer.Keys);
            keys.Sort();
            Console.WriteLine(indexer.MaxIndex + " " + String.Join(",", keys));
        }
        
        public IEnumerable<string> Keys
        {
            get
            {
                return _map.Keys;
            }
        }
        
        private class Record
        {
            private readonly Indexer _indexer;
            private int _index = -1;
            
            public Record(Indexer indexer)
            {
                _indexer = indexer;
            }
            
            public int Index
            {
                get
                {
                    if (_index >= 0)
                    {
                        return _index;
                    }
                    
                    lock (this)
                    {
                        if (_index < 0)
                        {
                            _index = Interlocked.Increment(ref _indexer._counter);
                        }
                        return _index;
                    }
                }
            }
        }
    }
}
Отредактировано 31.01.2015 4:32 AJ . Предыдущая версия .
Re: Thread-safe словарь с авто-инкрементируемым значением
От: frymode  
Дата: 31.01.15 09:04
Оценка:
Здравствуйте, AutumnLeaf, Вы писали:

AL>
AL>            public int Index
AL>            {
AL>                get
AL>                {
AL>                    if (_index >= 0)
AL>                    {
AL>                        return _index;
AL>                    }
                    
AL>                    lock (this)
AL>                    {
AL>                        if (_index < 0)
AL>                        {
AL>                            _index = Interlocked.Increment(ref _indexer._counter);
AL>                        }
AL>                        return _index;
AL>                    }
AL>                }
AL>            }
AL>

Менять значение внутри getter-а не самая лучшая идея, тем более мешая в одну кучу несинхронизированный доступ, lock и interlocked операции.
Лучше наверное передавать в конструктор Record сразу значение счётчика:

    return _map.GetOrAdd(key, k => new Record(Interlocked.Increment(ref _counter))).Index;
Re: Thread-safe словарь с авто-инкрементируемым значением
От: scale_tone Норвегия https://scale-tone.github.io/
Дата: 31.01.15 12:39
Оценка:
Здравствуйте, AutumnLeaf, Вы писали:

AL>Написал вот такой код, просьба подсказать, если есть более оптимальный вариант:


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

Инкрементировать индекс надо по факту успешного добавления новой строки:


    public interface IIndexer
    {
        ICollection<string> Keys { get; }
        int GetIndex(string key);
        int MaxIndex { get; }
    }

    public class AnotherIndexer : ConcurrentDictionary<string, int>, IIndexer
    {
        private int _counter = -1;

        public int GetIndex(string key)
        {
            if (!this.TryAdd(key, 0))
            {
                return this[key];
            }

            int index = Interlocked.Increment(ref _counter);
            this[key] = index;
            return index;
        }

        public int MaxIndex
        {
            get { return this._counter; }
        }
    }


В такой реализации только что добавленная строка да, будет некоторое время лежать в словаре с индексом 0. Но как я понял из задачи, для Вас это некритично. А если критично — вот тогда либо нужен лок (на весь словарь, а не на одну запись в нем, как у Вас), либо долго думать, как без него обойтись.
Re[2]: Thread-safe словарь с авто-инкрементируемым значением
От: scale_tone Норвегия https://scale-tone.github.io/
Дата: 31.01.15 14:38
Оценка:
Здравствуйте, scale_tone, Вы писали:


_> А если критично — вот тогда либо нужен лок (на весь словарь, а не на одну запись в нем, как у Вас), либо долго думать, как без него обойтись.


Впрочем, что тут думать:

    public class AnotherIndexer : ConcurrentDictionary<string, int>, IIndexer
    {
        private int _counter = -1;
        private const int TempIndexValue = -1;

        public int GetIndex(string key)
        {
            int index;

            if (!this.TryAdd(key, TempIndexValue))
            {
                while(true)
                {
                    index = this[key];
                    if (index == TempIndexValue)
                    {
                        Thread.Sleep(0);
                    }
                    else
                    {
                        return index;
                    }
                } 
            }

            index = Interlocked.Increment(ref _counter);
            this[key] = index;
            return index;
        }

        public int MaxIndex
        {
            get { return this._counter; }
        }
    }
Re[2]: Thread-safe словарь с авто-инкрементируемым значением
От: AutumnLeaf Великобритания  
Дата: 31.01.15 15:17
Оценка:
Здравствуйте, frymode, Вы писали:

F>Менять значение внутри getter-а не самая лучшая идея, тем более мешая в одну кучу несинхронизированный доступ, lock и interlocked операции.

F>Лучше наверное передавать в конструктор Record сразу значение счётчика:

F>
F>    return _map.GetOrAdd(key, k => new Record(Interlocked.Increment(ref _counter))).Index;
F>


Насколько я понял документацию, фабрика может быть вызвана несколько раз, но только один результат попадёт в словарь. Соответственно возможны несколько инкрементов счётчика вхолостую, нет?
Re[2]: Thread-safe словарь с авто-инкрементируемым значением
От: AutumnLeaf Великобритания  
Дата: 31.01.15 15:23
Оценка:
Здравствуйте, scale_tone, Вы писали:

_>Здравствуйте, AutumnLeaf, Вы писали:


AL>>Написал вот такой код, просьба подсказать, если есть более оптимальный вариант:


_>В Вашем коде ошибка: делегат, передаваемый в GetOrAdd(), вполне может выполниться несколько раз "вхолостую". Что приведет как раз к "дыркам в счетчике".


Да, я знал что там может быть создано несколько объектов Record, но Index-то мы достаём позже и он будет использован только в одном из них. Если Record создан, но никто к свойству Index не обращался, то и дырок не должно быть.



_>Здравствуйте, AutumnLeaf, Вы писали:


_>Инкрементировать индекс надо по факту успешного добавления новой строки:


_>

_>    public interface IIndexer
_>    {
_>        ICollection<string> Keys { get; }
_>        int GetIndex(string key);
_>        int MaxIndex { get; }
_>    }

_>    public class AnotherIndexer : ConcurrentDictionary<string, int>, IIndexer
_>    {
_>        private int _counter = -1;

_>        public int GetIndex(string key)
_>        {
_>            if (!this.TryAdd(key, 0))
_>            {
_>                return this[key];
_>            }

_>            int index = Interlocked.Increment(ref _counter);
_>            this[key] = index;
_>            return index;
_>        }

_>        public int MaxIndex
_>        {
_>            get { return this._counter; }
_>        }
_>    }

_>


_>В такой реализации только что добавленная строка да, будет некоторое время лежать в словаре с индексом 0. Но как я понял из задачи, для Вас это некритично. А если критично — вот тогда либо нужен лок (на весь словарь, а не на одну запись в нем, как у Вас), либо долго думать, как без него обойтись.


Критично, я эти индексы потом использую для нумерации в массиве. Но идея хорошая, я про наследование от ConcurrentDictionary не подумал.
Re[3]: Thread-safe словарь с авто-инкрементируемым значением
От: AutumnLeaf Великобритания  
Дата: 31.01.15 15:30
Оценка:
Здравствуйте, scale_tone, Вы писали:

_>Здравствуйте, scale_tone, Вы писали:



_>> А если критично — вот тогда либо нужен лок (на весь словарь, а не на одну запись в нем, как у Вас), либо долго думать, как без него обойтись.


_>Впрочем, что тут думать:


_>
_>    public class AnotherIndexer : ConcurrentDictionary<string, int>, IIndexer
_>    {
_>        private int _counter = -1;
_>        private const int TempIndexValue = -1;

_>        public int GetIndex(string key)
_>        {
_>            int index;

_>            if (!this.TryAdd(key, TempIndexValue))
_>            {
_>                while(true)
_>                {
_>                    index = this[key];
_>                    if (index == TempIndexValue)
_>                    {
_>                        Thread.Sleep(0);
_>                    }
_>                    else
_>                    {
_>                        return index;
_>                    }
_>                } 
_>            }

_>            index = Interlocked.Increment(ref _counter);
_>            this[key] = index;
_>            return index;
_>        }

_>        public int MaxIndex
_>        {
_>            get { return this._counter; }
_>        }
_>    }
_>



Должно работать по идее, интересно будет сравнить производительность с моим исходным вариантом
Re[3]: Thread-safe словарь с авто-инкрементируемым значением
От: scale_tone Норвегия https://scale-tone.github.io/
Дата: 31.01.15 15:47
Оценка:
Здравствуйте, AutumnLeaf, Вы писали:

AL>Да, я знал что там может быть создано несколько объектов Record, но Index-то мы достаём позже и он будет использован только в одном из них. Если Record создан, но никто к свойству Index не обращался, то и дырок не должно быть.


А, ну да, действительно. Это я не подумал, виноват.
Re: Thread-safe словарь с авто-инкрементируемым значением
От: Lexey Россия  
Дата: 02.02.15 12:40
Оценка: +1
Здравствуйте, AutumnLeaf, Вы писали:

AL> private int _counter = -1;


Тут стоит добавить volatile.

AL> t1.Join();

AL> t2.Join();
AL> t3.Join();
AL> t4.Join();

Тут потокам Dispose желательно cделать.

AL> lock (this)

AL> {
AL> if (_index < 0)
AL> {
AL> _index = Interlocked.Increment(ref _indexer._counter);
AL> }
AL> return _index;
AL> }

Тут лучше Lazy<> использовать, а не городить такой огород.
"Будь достоин победы" (c) 8th Wizard's rule.
Re: Thread-safe словарь с авто-инкрементируемым значением
От: hardcase Пират http://nemerle.org
Дата: 02.02.15 14:02
Оценка:
Здравствуйте, AutumnLeaf, Вы писали:

AL>Производительность, конечно, требуется выше, чем в случае если каждый метод сихронизован в лоб.


Есть такой код, на нагрузке не тестировался:
  public module StringIndex
  {
    private _initialTableSize = 1024;

    private _tableLock     : object = object();
    private mutable _table : array[string] = array(_initialTableSize);
    private mutable _index : int;

    private _internTable : ConcurrentDictionary[string, int] = ConcurrentDictionary(Environment.ProcessorCount * 4, _initialTableSize, StringComparer.InvariantCulture);

    public GetId(text : string) : int
    {
      def internTable = _internTable;
      mutable result;
      when (internTable.TryGetValue(text, out result))
        return result;

      lock (_tableLock)
      {
        when (internTable.TryGetValue(text, out result))
          return result;

        def id = _index + 1;
        when (id >= _table.Length)
          Array.Resize(ref _table, _table.Length * 2);
        _table[id] = text;
        _index = id;
        internTable.GetOrAdd(text, id)
      }
    }

    public GetText(id : int) : string
    {
      _table[id]
    }
  }
http://nemerle.org/Banners/?t=Developer!&g=dark /* иЗвиНите зА неРовнЫй поЧерК */
Re[2]: Thread-safe словарь с авто-инкрементируемым значением
От: AutumnLeaf Великобритания  
Дата: 02.02.15 19:11
Оценка:
Здравствуйте, Lexey, Вы писали:

L>Здравствуйте, AutumnLeaf, Вы писали:


AL>> private int _counter = -1;


L>Тут стоит добавить volatile.


А что будет если не добавлять? Я так понимаю, что в худшем случае потоку, который обращается к этому индексу впервые, придётся сделать lock один раз, после чего он увидит правильное значение и может его кэшировать где угодно, потому что оно больше меняться не будет. Если у нас много новых потоков постоянно рождаются, то это может быть проблемой, но если пул в целом один и тот же, то отсутствие volatile может быть более эффективным, чем каждый раз вычитывать значение из основной памяти. Хотя может я и занимаюсь преждевременной оптимизацией.


AL>> t1.Join();

AL>> t2.Join();
AL>> t3.Join();
AL>> t4.Join();

L>Тут потокам Dispose желательно cделать.


А как? Не нашёл такого метода.


AL>> lock (this)

AL>> {
AL>> if (_index < 0)
AL>> {
AL>> _index = Interlocked.Increment(ref _indexer._counter);
AL>> }
AL>> return _index;
AL>> }

L>Тут лучше Lazy<> использовать, а не городить такой огород.


С одной стороны согласен, что лучше использовать готовое решение, с другой там внутри Lazy огород ещё покруче нагорожен
Re[2]: Thread-safe словарь с авто-инкрементируемым значением
От: AutumnLeaf Великобритания  
Дата: 02.02.15 19:14
Оценка:
Здравствуйте, hardcase, Вы писали:

H>Здравствуйте, AutumnLeaf, Вы писали:


AL>>Производительность, конечно, требуется выше, чем в случае если каждый метод сихронизован в лоб.


H>Есть такой код, на нагрузке не тестировался:

H>
H>  public module StringIndex
H>  {
H>    private _initialTableSize = 1024;

H>    private _tableLock     : object = object();
H>    private mutable _table : array[string] = array(_initialTableSize);
H>    private mutable _index : int;

H>    private _internTable : ConcurrentDictionary[string, int] = ConcurrentDictionary(Environment.ProcessorCount * 4, _initialTableSize, StringComparer.InvariantCulture);

H>    public GetId(text : string) : int
H>    {
H>      def internTable = _internTable;
H>      mutable result;
H>      when (internTable.TryGetValue(text, out result))
H>        return result;

H>      lock (_tableLock)
H>      {
H>        when (internTable.TryGetValue(text, out result))
H>          return result;

H>        def id = _index + 1;
H>        when (id >= _table.Length)
H>          Array.Resize(ref _table, _table.Length * 2);
H>        _table[id] = text;
H>        _index = id;
H>        internTable.GetOrAdd(text, id)
H>      }
H>    }

H>    public GetText(id : int) : string
H>    {
H>      _table[id]
H>    }
H>  }
H>



На первый взгляд кажется, что есть вероятность, что GetText может по конкретному индексу читать null, даже если там есть какое-то значение, поскольку синхронизации никакой нет, а ячейка массива сама по себе не volatile. Или это в Вашем приложении не проблема?
Re[3]: Thread-safe словарь с авто-инкрементируемым значением
От: hardcase Пират http://nemerle.org
Дата: 03.02.15 10:03
Оценка:
Здравствуйте, AutumnLeaf, Вы писали:

AL>На первый взгляд кажется, что есть вероятность, что GetText может по конкретному индексу читать null, даже если там есть какое-то значение, поскольку синхронизации никакой нет, а ячейка массива сама по себе не volatile. Или это в Вашем приложении не проблема?


Полный барьер памяти делает lock, а кэши процессора вроде как когерентны.
http://nemerle.org/Banners/?t=Developer!&g=dark /* иЗвиНите зА неРовнЫй поЧерК */
Re: Thread-safe словарь с авто-инкрементируемым значением
От: Sinix  
Дата: 03.02.15 14:44
Оценка: 10 (2)
Здравствуйте, AutumnLeaf, Вы писали:

AL>Дисклеймер: всегда писал на Java и только недавно стал пользоваться C#, так что просьба не обращать внимание на стиль


AL>Для решения одной задачи понадобилось написать такой словарь, который бы было можно использовать из разных потоков и который бы реализовывал вот такой интерфейс


Подход в лоб — Lazy<T>, ваш record его почти реализовал. Обычно он невыгоден по памяти и по аллокациям, но надо смотреть на реальной трассе, может там копейки в общей сумме выходят.

Можно обойтись старым-добрым double-check-lock + (для эстетов) выборочными блокировками.

Поиграйтесь с uniqCount/totalCount — увидите разницу.
   Original:   190ms, ips:   5 290,65 | Mem:   587,41 kb  GC0:  205 =>  1 008
       Lazy:   201ms, ips:   5 008,56 | Mem:   743,68 kb  GC0:  205 =>  1 008
DoubleCheck:   153ms, ips:   6 573,46 | Mem:   120,78 kb  GC0:    0 =>  1 008
      Naive:   452ms, ips:   2 226,75 | Mem:   173,10 kb  GC0:    0 =>  1 008
Done.


  код
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

public class Program
{
    public interface IIndexer
    {
        IEnumerable<string> Keys { get; }
        int GetIndex(string key);
        int MaxIndex { get; }
    }

    public class Indexer : IIndexer
    {
        private readonly ConcurrentDictionary<string, Record> _map =
            new ConcurrentDictionary<string, Record>();

        private int _counter = -1;

        public int GetIndex(string key)
        {
            return _map.GetOrAdd(key, k => new Record(this)).Index;
        }

        public int MaxIndex { get { return _counter; } }

        public IEnumerable<string> Keys
        {
            get
            {
                return _map.Keys;
            }
        }

        private class Record
        {
            private readonly Indexer _indexer;
            private int _index = -1;

            public Record(Indexer indexer)
            {
                _indexer = indexer;
            }

            public int Index
            {
                get
                {
                    if (_index >= 0)
                    {
                        return _index;
                    }

                    lock (this)
                    {
                        if (_index < 0)
                        {
                            _index = Interlocked.Increment(ref _indexer._counter);
                        }
                        return _index;
                    }
                }
            }
        }
    }
    public class LazyIndexer : IIndexer
    {
        private readonly ConcurrentDictionary<string, Lazy<int>> _map =
            new ConcurrentDictionary<string, Lazy<int>>();

        private int _counter = -1;

        private Lazy<int> GetLazy()
        {
            return new Lazy<int>(() => Interlocked.Increment(ref _counter), LazyThreadSafetyMode.ExecutionAndPublication);
        }

        public int GetIndex(string key)
        {
            return _map.GetOrAdd(key, k => GetLazy()).Value;
        }

        public int MaxIndex { get { return _counter; } }

        public IEnumerable<string> Keys
        {
            get
            {
                return _map.Keys;
            }
        }
    }
    public class DoubleCheckIndexer : IIndexer
    {
        private readonly ConcurrentDictionary<string, int> _map =
            new ConcurrentDictionary<string, int>();

        private int _counter = -1;

        private object[] _lockKeys = Enumerable.Range(0, 39).Select(_ => new object()).ToArray();

        private Lazy<int> GetLazy()
        {
            return new Lazy<int>(() => Interlocked.Increment(ref _counter), LazyThreadSafetyMode.ExecutionAndPublication);
        }

        public int GetIndex(string key)
        {
            int result;
            if (!_map.TryGetValue(key, out result))
            {
                var hash = Math.Abs(key.GetHashCode());
                lock (_lockKeys[hash % _lockKeys.Length])
                {
                    if (!_map.TryGetValue(key, out result))
                    {
                        result = Interlocked.Increment(ref _counter);
                        _map[key] = result;
                    }
                }
            }
            return result;
        }

        public int MaxIndex { get { return _counter; } }

        public IEnumerable<string> Keys
        {
            get
            {
                return _map.Keys;
            }
        }
    }

    public static void Main()
    {
        int totalCount = 10 * 1000 * 1000;
        int uniqCount = 1009; // nearest prime to simulate uneven load;
        var keys = Enumerable
            .Range(1, totalCount)
            .Select(i => (i % uniqCount).ToString()).ToArray();

        Measure("Original", () =>
        {
            var ix = new Indexer();
            Parallel.ForEach(keys, k => ix.GetIndex(k));
            return ix.MaxIndex;
        });

        Measure("Lazy", () =>
        {
            var ix = new LazyIndexer();
            Parallel.ForEach(keys, k => ix.GetIndex(k));
            return ix.MaxIndex;
        });

        Measure("DoubleCheck", () =>
        {
            var ix = new DoubleCheckIndexer();
            Parallel.ForEach(keys, k => ix.GetIndex(k));
            return ix.MaxIndex;
        });


        Measure("Naive", () =>
        {
            var data = keys
                .Distinct()
                .Select((s, i) => new { s, i })
                .ToDictionary(x => x.s, x => x.i);
            return data.Count - 1;
        });

        Console.Write("Done.");
        Console.ReadKey();
    }

    static void Measure(string name, Func<long> callback)
    {
        GC.Collect();
        GC.WaitForPendingFinalizers();
        GC.Collect();

        var mem = GC.GetTotalMemory(true);
        var gc = GC.CollectionCount(0);

        var sw = Stopwatch.StartNew();
        var result = callback();
        sw.Stop();

        var mem2 = GC.GetTotalMemory(false);
        var gc2 = GC.CollectionCount(0);

        var memDelta = (mem2 - mem) / 1024.0;
        var gcDelta = gc2 - gc;

        Console.WriteLine(
            "{0,11}: {1,5}ms, ips: {2,10:N} | Mem: {3,8:N2} kb  GC0: {4,4} => {5,6:N0}",
            name, sw.ElapsedMilliseconds, result / sw.Elapsed.TotalSeconds, memDelta, gcDelta, result);
    }
}


Код на корректность толком не проверял, могут быть глупые опечатки.
Re[4]: Thread-safe словарь с авто-инкрементируемым значением
От: AutumnLeaf Великобритания  
Дата: 04.02.15 16:08
Оценка:
Здравствуйте, hardcase, Вы писали:

H>Здравствуйте, AutumnLeaf, Вы писали:


AL>>На первый взгляд кажется, что есть вероятность, что GetText может по конкретному индексу читать null, даже если там есть какое-то значение, поскольку синхронизации никакой нет, а ячейка массива сама по себе не volatile. Или это в Вашем приложении не проблема?


H>Полный барьер памяти делает lock, а кэши процессора вроде как когерентны.


Но GetText лок не использует и, следовательно, с (однопоточной) точки зрения того потока, который вызывает GetText, но не вызывает GetIndex, массив со строками не может измениться. Соответственно он может сколь угодно долго считать, что там лежит null.
Re[2]: Thread-safe словарь с авто-инкрементируемым значением
От: AutumnLeaf Великобритания  
Дата: 04.02.15 16:10
Оценка:
Здравствуйте, Sinix, Вы писали:

S>Подход в лоб — Lazy<T>, ваш record его почти реализовал. Обычно он невыгоден по памяти и по аллокациям, но надо смотреть на реальной трассе, может там копейки в общей сумме выходят.


S>Можно обойтись старым-добрым double-check-lock + (для эстетов) выборочными блокировками.


S>Поиграйтесь с uniqCount/totalCount — увидите разницу.

S>
S>   Original:   190ms, ips:   5 290,65 | Mem:   587,41 kb  GC0:  205 =>  1 008
S>       Lazy:   201ms, ips:   5 008,56 | Mem:   743,68 kb  GC0:  205 =>  1 008
S>DoubleCheck:   153ms, ips:   6 573,46 | Mem:   120,78 kb  GC0:    0 =>  1 008
S>      Naive:   452ms, ips:   2 226,75 | Mem:   173,10 kb  GC0:    0 =>  1 008
S>Done.
S>

S>Код на корректность толком не проверял, могут быть глупые опечатки.

Спасибо за код, поиграю. В принципе коллекции небольшие и их не так много, поэтому оверхэд на Record не должен быть значительным.
Не ожидал, если честно, что DoubleCheck будет быстрее.
Отредактировано 04.02.2015 16:14 AJ . Предыдущая версия .
Re[3]: Thread-safe словарь с авто-инкрементируемым значением
От: Sinix  
Дата: 04.02.15 16:34
Оценка:
Здравствуйте, AutumnLeaf, Вы писали:

AL>Спасибо за код, поиграю. В принципе коллекции небольшие и их не так много, поэтому оверхэд на Record не должен быть значительным.

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

AL>Не ожидал, если честно, что DoubleCheck будет быстрее.

Надо бы проверить на реальном коде, пример показывает худший случай, когда других узких мест нет.
Re[5]: Thread-safe словарь с авто-инкрементируемым значением
От: hardcase Пират http://nemerle.org
Дата: 04.02.15 16:40
Оценка: +1 -1
Здравствуйте, AutumnLeaf, Вы писали:

AL>Но GetText лок не использует и, следовательно, с (однопоточной) точки зрения того потока, который вызывает GetText, но не вызывает GetIndex, массив со строками не может измениться. Соответственно он может сколь угодно долго считать, что там лежит null.


Это если кэши не когерентны.
http://nemerle.org/Banners/?t=Developer!&g=dark /* иЗвиНите зА неРовнЫй поЧерК */
Re[6]: Thread-safe словарь с авто-инкрементируемым значением
От: AutumnLeaf Великобритания  
Дата: 05.02.15 00:13
Оценка: -1
Здравствуйте, hardcase, Вы писали:

H>Здравствуйте, AutumnLeaf, Вы писали:


AL>>Но GetText лок не использует и, следовательно, с (однопоточной) точки зрения того потока, который вызывает GetText, но не вызывает GetIndex, массив со строками не может измениться. Соответственно он может сколь угодно долго считать, что там лежит null.


H>Это если кэши не когерентны.


Это только для x86/x64 процессоров выполняется? Когерентность кэшей.
А что если компилятор там что-нибудь соптимизирует и до процессора в данном случае дело не дойдёт?

Не совсем ещё понимаю, наличие лока в GetId как-то влияет на GetText или нет? Что достигается барьером памяти? Я так понял из статей, что полный барьер только предотвращает reordering вокруг него, но сам по себе ещё не гарантирует flush в память (хотя вот тут написано, что в C# любая запись flush'ится в память, но это memory barrier'у я так понял ортогонально).
Re[7]: Thread-safe словарь с авто-инкрементируемым значением
От: hardcase Пират http://nemerle.org
Дата: 05.02.15 13:33
Оценка:
Здравствуйте, AutumnLeaf, Вы писали:

AL>Это только для x86/x64 процессоров выполняется? Когерентность кэшей.


Для x86/x64 да, для остальных нужно читать.

AL>А что если компилятор там что-нибудь соптимизирует и до процессора в данном случае дело не дойдёт?


Не очень понятно, как можно оптимизировать обращение к изменяемой статической переменной (поле _table).

AL>Не совсем ещё понимаю, наличие лока в GetId как-то влияет на GetText или нет? Что достигается барьером памяти? Я так понял из статей, что полный барьер только предотвращает reordering вокруг него, но сам по себе ещё не гарантирует flush в память (хотя вот тут написано, что в C# любая запись flush'ится в память, но это memory barrier'у я так понял ортогонально).


При выходе из блокировки (Monitor.Exit) срабатывает барьер памяти (полный) — происходят все отложенные операции записи в память (чтение в нашем случае не интересно).
В случае, когда массив _table имеет достаточный размер, происходит единичное изменение по какому-то адресу внутри этого массива. Если значение по этому адресу памяти (там ранее лежал null) закешировано в другом ядре процессора, то этот кэш будет обновлен — это называется когерентность. Когда поток, работающий на этом ядре получит новый Id, он сможет получить для него правильный Text (но assert(str : object != null) я все же добавлю в код).

В случае, когда размер массива _table недостаточен, будет изменена сама переменная _table. До завершения блокировки ни один поток, работающий со StringIndex не имеет новых Id и потому они могут безопасно работать как со старой, так и с новой версией массива. К моменту получения другим потоком нового Id кэши уже будут синхронизированы и он будет работать с версией массива, в котором есть этот индекс.

Тонкий момент здесь еще в том, что указатели в x86/x64 атомарны и пишутся/читаются процессором в один прием (во всяком случае я так считаю). Если бы работа шла со структурами бОльших размеров, то потребовалась бы синхронизация, чтобы не получить одну часть структуры старой версии, а другую — новой.
http://nemerle.org/Banners/?t=Developer!&g=dark /* иЗвиНите зА неРовнЫй поЧерК */
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.