using System.Numerics;
namespace test_bit_masks;
internal class Program
{
private const int _bitsShiftUlong = 6;
private const int _bitsPerByte = 8;
private const int _bitsPerUlong = sizeof(ulong) * _bitsPerByte;
static void Main(string[] args)
{
var randomFillPercentage = 30;
var minSequenceLength = 1;
var maxSequenceLength = byte.MaxValue;
var bitsQuantity = ushort.MaxValue;
var testsQuantity = 1_000;
var bits = new ulong[(int)((uint)(bitsQuantity - 1 + (1 << _bitsShiftUlong)) >> _bitsShiftUlong)];
RandomFill(randomFillPercentage, bitsQuantity, ref bits);
foreach (var _ in Enumerable.Range(0, testsQuantity))
{
var requiredQty = Random.Shared.Next(minSequenceLength, maxSequenceLength);
var start = Random.Shared.Next(0, bitsQuantity);
var res = TryFindFreeSlotsNewVersion(start, bitsQuantity, requiredQty, ref bits, out var shift, false);
}
Console.WriteLine($"Done");
Console.ReadLine();
}
private static void RandomFill(int fillPercentage, int bitsQuantity, ref ulong[] bits)
{
var number = bitsQuantity * fillPercentage / 100;
var rnd = Random.Shared;
foreach (var i in Enumerable.Range(0, number))
{
var index = rnd.Next(0, bitsQuantity);
bits[index >> _bitsShiftUlong] |= 1ul << index;
}
}
private static bool TryFindFreeSlotsNewVersion(int start, int bitsQuantity, int requiredQuantity, ref ulong[] bits, out int shift, bool debug = false)
{
var position = start;
var candidateShift = 0;
var lastArrayIndex = bits.Length - 1;
var lastArrayItemBitsToReset = bits.Length * _bitsPerUlong - bitsQuantity;
var testShift = 0;
var startAdjusted = false;
var lastPosition = start + bitsQuantity;
var top = Console.CursorTop;
var remainingQuantity = requiredQuantity;
var partialCapture = false;
var found = false;
while (!found)
{
position = start + testShift;
if (position >= lastPosition) break;
if (debug)
{
Console.CursorTop = top;
Console.WriteLine();
}
var bufferPosition = (start + testShift) % bitsQuantity;
var arrayItemIndex = bufferPosition >> _bitsShiftUlong;
var v = bits[arrayItemIndex];
var mask = 1UL << bufferPosition;
var maskForValue = mask | ~(mask - 1);
var arrayItemPosition = bufferPosition % _bitsPerUlong;
var maskedValue = v & maskForValue;
if (debug)
{
Console.WriteLine(new string(Convert.ToString((long)v, 2).PadLeft(_bitsPerUlong, '0').Reverse().ToArray()));
Console.WriteLine(new string(Convert.ToString((long)maskForValue, 2).PadLeft(_bitsPerUlong, '0').Reverse().ToArray()));
Console.WriteLine(new string(Convert.ToString((long)maskedValue, 2).PadLeft(_bitsPerUlong, '0').Reverse().ToArray()));
Console.WriteLine(new string(Convert.ToString((long)(1UL << arrayItemPosition), 2).PadLeft(_bitsPerUlong, '0').Replace("0", " ").Replace("1", "↑").Reverse().ToArray()));
}
if (debug)
{
Console.ReadKey();
}
var isLastArrayIndex = arrayItemIndex == lastArrayIndex;
var maximumCount = BitOperations.PopCount(maskForValue);
var totalFreeCount = maximumCount - BitOperations.PopCount(maskedValue) - (isLastArrayIndex ? lastArrayItemBitsToReset : 0);
var trailingZeroCount = BitOperations.TrailingZeroCount(maskedValue);
var availableFreeSlotsForCurrentPosition = trailingZeroCount - arrayItemPosition;
var isOnLastZeroes = availableFreeSlotsForCurrentPosition == maximumCount;
if (isOnLastZeroes && isLastArrayIndex)
{
availableFreeSlotsForCurrentPosition = availableFreeSlotsForCurrentPosition - lastArrayItemBitsToReset;
}
if (partialCapture && availableFreeSlotsForCurrentPosition == _bitsPerUlong)
{
if (!isLastArrayIndex)
{
remainingQuantity -= availableFreeSlotsForCurrentPosition;
testShift += availableFreeSlotsForCurrentPosition;
}
else
{
partialCapture = false;
remainingQuantity = requiredQuantity;
}
}
else if (partialCapture && availableFreeSlotsForCurrentPosition < remainingQuantity)
{
partialCapture = false;
remainingQuantity = requiredQuantity;
}
else if (partialCapture && availableFreeSlotsForCurrentPosition >= remainingQuantity)
{
found = true;
}
else
{
if (!startAdjusted || (totalFreeCount >= remainingQuantity || isOnLastZeroes))
{
if (availableFreeSlotsForCurrentPosition >= remainingQuantity)
{
candidateShift = testShift;
found = true;
}
else if (availableFreeSlotsForCurrentPosition == 0)
{
if (!startAdjusted)
{
startAdjusted = true;
if (testShift > 0)
{
lastPosition = lastPosition + testShift - 1;
}
}
testShift++;
}
else if (availableFreeSlotsForCurrentPosition < remainingQuantity)
{
if (isOnLastZeroes && !isLastArrayIndex)
{
candidateShift = testShift;
remainingQuantity -= availableFreeSlotsForCurrentPosition;
partialCapture = true;
}
testShift += availableFreeSlotsForCurrentPosition;
}
}
else
{
var leadingZeroCount = BitOperations.LeadingZeroCount(maskedValue);
if (isLastArrayIndex)
{
leadingZeroCount = leadingZeroCount - lastArrayItemBitsToReset;
testShift += maximumCount - lastArrayItemBitsToReset - leadingZeroCount;
}
else
{
testShift += maximumCount - leadingZeroCount;
}
}
}
}
shift = candidateShift;
return found;
}
}using System.Runtime.CompilerServices;
namespace test_range_locking;
internal class Program
{
private readonly Random _random = Random.Shared;
private const int _bufferSize = 20;
private byte[] _buffer = new byte[_bufferSize];
private RangeLocker _locker;
private readonly int _tasksQty;
private readonly int _loopsQty;
public Program(int tasksQty, int loopsQty)
{
_tasksQty = tasksQty;
_loopsQty = loopsQty;
}
static void Main(string[] args)
{
new Program(3, 3).Run();
Console.WriteLine("Done");
Console.ReadLine();
}
private void Run()
{
_locker = new RangeLocker(_bufferSize, 4);
var padding = _tasksQty.ToString().Length;
var tasks = Enumerable.Range(0, _tasksQty)
.Select(i => Task.Run(() => InternalTask($"{i}".PadLeft(padding, ' '), _loopsQty)))
.ToArray();
Task.WaitAll(tasks);
}
private void InternalTask(string taskId, int loops)
{
for (var idx = loops - 1; idx >= 0; idx--)
{
var start = _random.Next(0, _bufferSize);
var len = _random.Next(1, _bufferSize - start + 1);
using (var @lock = _locker.Aquire(taskId, start, len))
{
Thread.Sleep(2000);
}
}
}
}
internal class RangeLocker
{
private readonly int _bufferSize;
private int[] _painterBuffer;
private ulong[] _parentIndices;
private RangeLock[] _locks;
private int _locksBufferSize;
private int _locksHead;
private int _locksQuantity;
private Semaphore _semaphoreFreeLocksQuantity;
private int _mainSpinLock;
public RangeLocker(int bufferSize, int maximumLocksQty)
{
_bufferSize = bufferSize;
_locksBufferSize = maximumLocksQty;
_painterBuffer = new int[_bufferSize];
_painterBuffer.AsSpan().Fill(-1);
_parentIndices = new ulong[BitUtils.GetRequiredNumberOfUlongs(_locksBufferSize)];
_locks = new RangeLock[_locksBufferSize];
_locksHead = 0;
_locksQuantity = 0;
_mainSpinLock = 0;
_semaphoreFreeLocksQuantity = new Semaphore(_locksBufferSize, _locksBufferSize);
}
internal IDisposable Aquire(string taskId, int offset, int length)
{
Console.WriteLine($"THR {taskId} -> Try {offset} -> {offset + length - 1}");
_semaphoreFreeLocksQuantity.WaitOne();
var notified = false;
while (Interlocked.CompareExchange(ref _mainSpinLock, 1, 0) != 0)
{
if (!notified)
{
Console.WriteLine($"THR {taskId} -> Waiting for Main");
notified = true;
}
}
Console.WriteLine($"THR {taskId} -> In Main");
var lockPosition = _locksHead;
ref var range = ref _locks[lockPosition];
var parentsUnlockEvents = GatherParents(offset, length, lockPosition, out var debugParents);
range.Lock(offset, length);
_locksHead = GetNextFreePosition(_locksHead);
Interlocked.Increment(ref _locksQuantity);
Console.WriteLine($"THR {taskId} -> Main Released -> Free: {_locksBufferSize - _locksQuantity}");
_mainSpinLock = 0;
if (parentsUnlockEvents.Length > 0)
{
Console.WriteLine($"THR {taskId} -> Waiting for parents: {debugParents}");
WaitHandle.WaitAll(parentsUnlockEvents);
Console.WriteLine($"THR {taskId} -> Parents released");
}
Console.WriteLine($"THR {taskId} -> LOCK {lockPosition}: {offset} -> {offset + length - 1}");
return new RangeUnlocker(this, lockPosition);
}
private ManualResetEvent[] GatherParents(int offset, int length, int lockPosition, out string debugParents)
{
debugParents = "";
BitUtils.SetAllFalse(_parentIndices);
var painterIndex = 0;
var candidateParent = -1;
for (var idx = length - 1; idx >= 0; idx--)
{
painterIndex = offset + idx;
candidateParent = _painterBuffer[painterIndex];
if (candidateParent >= 0)
{
BitUtils.SetBitTrue(candidateParent, _parentIndices);
}
_painterBuffer[painterIndex] = lockPosition;
}
var parentsQty = BitUtils.GetIndexesForPositivesCount(_parentIndices);
var parentsUnlockEvents = default(List<ManualResetEvent>);
var parentsStr = "";
if (parentsQty > 0)
{
var usedParentIndices = new List<int>();
parentsUnlockEvents = new List<ManualResetEvent>();
var parentsIndices = BitUtils.GetIndexesForPositives(_parentIndices);
var parentIndex = -1;
for (var idx = parentsQty - 1; idx >= 0; idx--)
{
parentIndex = parentsIndices[idx];
ref var parent = ref _locks[parentIndex];
if (parent.Locked)
{
usedParentIndices.Add(parentIndex);
parentsUnlockEvents.Add(parent.UnlockEvent);
}
}
parentsQty = parentsUnlockEvents.Count;
if (parentsQty > 0)
{
debugParents = string.Join(", ", usedParentIndices);
}
}
BitUtils.SetAllFalse(_parentIndices);
return parentsQty > 0 ? parentsUnlockEvents.ToArray() : Array.Empty<ManualResetEvent>();
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private int GetNextFreePosition(int position)
{
var foundPosition = GetBufferPosition(position + 1);
while (_locks[foundPosition].Locked)
{
foundPosition = GetBufferPosition(foundPosition + 1);
}
return foundPosition;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private int GetBufferPosition(int position)
{
return position % _locksBufferSize;
}
private void Release(int lockPosition)
{
var notified = false;
while (Interlocked.CompareExchange(ref _mainSpinLock, 1, 0) != 0)
{
if (!notified)
{
Console.WriteLine($"UNLOCK {lockPosition} -> Waiting for Main");
notified = true;
}
}
Console.WriteLine($"UNLOCK {lockPosition} -> In Main");
ref var range = ref _locks[lockPosition];
var offset = range.Offset;
var painterIndex = 0;
for (var idx = range.Length - 1; idx >= 0; idx--)
{
painterIndex = offset + idx;
if (_painterBuffer[painterIndex] == lockPosition)
{
_painterBuffer[painterIndex] = -1;
}
}
Console.WriteLine($"UNLOCK {lockPosition}: {range.Offset} -> {range.Offset + range.Length - 1}");
range.Unlock();
Interlocked.Decrement(ref _locksQuantity);
Console.WriteLine($"UNLOCK {lockPosition} -> Main Released -> Free: {_locksBufferSize - _locksQuantity}");
_semaphoreFreeLocksQuantity.Release();
Console.WriteLine($"UNLOCK {lockPosition} -> Semaphore.Release()");
_mainSpinLock = 0;
Console.WriteLine($"UNLOCK {lockPosition} -> Release()");
}
private struct RangeLock
{
public ManualResetEvent UnlockEvent { get; private set; }
public bool Locked { get; private set; }
public int Offset { get; private set; }
public int Length { get; private set; }
private bool _initialized = false;
public RangeLock()
{
}
private void Initialize()
{
if (!_initialized)
{
UnlockEvent = new ManualResetEvent(true);
Locked = false;
_initialized = true;
}
}
public void Lock(int offset, int length)
{
Initialize();
if (Locked)
{
throw new Exception("Already locked");
}
UnlockEvent.Reset();
Locked = true;
Offset = offset;
Length = length;
}
public void Unlock()
{
if (!Locked)
{
throw new Exception("Already unlocked");
}
UnlockEvent.Set();
Locked = false;
}
}
private class RangeUnlocker : IDisposable
{
private bool _disposed;
private readonly RangeLocker _locker;
private readonly int _lockPosition;
public RangeUnlocker(RangeLocker locker, int lockPosition)
{
_locker = locker;
_lockPosition = lockPosition;
}
protected virtual void Dispose(bool disposing)
{
if (!_disposed)
{
if (disposing)
{
_locker.Release(_lockPosition);
}
_disposed = true;
}
}
public void Dispose()
{
Dispose(disposing: true);
GC.SuppressFinalize(this);
}
}
}var strings = new string[]; //25 млн записей
var words = new Dictionary<string,HashSet<int>>();
//формирование "справочника"
var str = string.Empty;
for(var stringId = strings.Length - 1; stringId >= 0; stringId--)
{
str = strings[stringId];
var stringWords = NormalizeString(str).Split(' ');
foreach(var stringWord in stringWords )
{
words[stringWord].Add(stringId);
}
}
//поиск
var searchTermWords= NormilizeString(searchTerm).Split(' ')
var foundIds = new HashSet<int>();
foreach(var searchTermWord in searchTermWords)
{
foreach(var matchWord in words.Keys.Where(x => x.Contains(searcgTermWord)))
{
if (words.TryGetValue(matchWord, out var stringIds))
{
if (foundIds == null)
{
foundIds = stringIds;
}
else
{
foundIds = stringIds.Where(x => foundIds .Contains(x)).ToHashSet();
}
}
else
{
foundIds = null;
}
}
}
Console.WriteLine($"Найдено строк: {foundIds.Count} ");Поиск: 100 циклов поиска 1-3 символьной подстроки по одному полю
records: ~5 000 000
TestContains (ms):
-> Max: 434, Avg: 295.56, Median: 281
TestSqliteFTS (ms):
CREATE -> 111
INSERT DATA -> 34697 //INSERT INTO temp_table(object_id, поле0, поле1, поле2, поле3)
INSERT INDEX -> 161683 // INSERT INTO fts_index(object_id, поле0, поле1, поле2, поле3 ) SELECT * FROM temp_table
DROP DATA -> 1191
VACUUM -> 15849
-> sqlite.db (FTS5: 1.6GB, tokenize = 'trigram', content='',columnsize=0, detail='column')
-> Max: 10, Avg: 1.16, Median: 0
TestWords (ms):
CREATE -> 89
INSERT DATA -> 98851 //INSERT INTO temp_table(word_id, object_id)
AGGREGATE DATA -> 28504 //SELET object_id FROM temp_table WHERE @word_id -> FastPFor -> INSERT word_id, object_ids_as_bytes
DROP DATA -> 1360
CREATE INDICES-> 9
VACUUM -> 262
-> sqlite.db (CUSTOM: 9.5MB, (tbl: fields -> id, value), (tbl: words -> id, field_id, value), (tbl: data -> word_id INTEGER, integersQty INTEGER, bytes BLOB))
-> Max: 128, Avg: 18.78, Median: 1
Статы:
field_id wordsQty maxRefsQty avgRefsQty maxRefsBytes avgRefsBytes
0 24075 6461929 271 910000 52
1 5339 23858735 4515 3336816 667
2 3602 6766040 1913 952808 295
3 11825 7595099 744 1069508 123
records: ~25 000 000
TestContains (ms):
-> Max: 2568, Avg: 1524.47, Median: 1437.5
TestSqliteFTS (ms):
CREATE -> 135
INSERT DATA -> 255882 //INSERT INTO temp_table(object_id, поле0, поле1, поле2, поле3)
INSERT INDEX -> 1022499 // INSERT INTO fts_index(object_id, поле0, поле1, поле2, поле3 ) SELECT * FROM temp_table
DROP DATA -> 370118
VACUUM -> 1230845
-> sqlite.db (FTS5: 8.1GB, tokenize = 'trigram', content='',columnsize=0, detail='column')
-> Max: 587, Avg: 11.53, Median: 0
TestWords (ms):
CREATE -> 107
INSERT DATA -> 581050 //INSERT INTO temp_table(word_id, object_id)
AGGREGATE DATA -> 132700 //SELET object_id FROM temp_table WHERE @word_id -> FastPFor -> INSERT word_id, object_ids_as_bytes
DROP DATA -> 6855
CREATE INDICES-> 32
VACUUM -> 1161
-> sqlite.db (CUSTOM: 35MB, (tbl: fields -> id, value), (tbl: words -> id, field_id, value), (tbl: data -> word_id INTEGER, integersQty INTEGER, bytes BLOB))
-> Max: 492, Avg: 64,87, Median: 1
Статы:
field_id wordsQty maxRefsQty avgRefsQty maxRefsBytes avgRefsBytes
0 24075 32570729 1355 4586324 205
1 5339 120257135 22577 16818780 3192
2 3602 34103240 9566 4802092 1372
3 11825 38282299 3723 5390372 542