I’m still wrapping my head around the proper usage of blobassets.
I was wondering if one can store a NativeHashMap in a blob asset, or if blob data has the same limitations as the data you can store inside an IComponentData.
At a high level, my goal is to store an immutable lookup table on my entity, which I can pass into jobs.
Thanks for any advice!
Blobs doesn’t support it at least as it’s currently implement but there’s no limitation for “BlobHashMap” to be implemented in the future
Well the way to do it is to put the keys and values as separate arrays in a blob asset and then read it at runtime to a hashmap. The BlobAsset as kind of a stream, like other streams will not support all data structures. Not that it is not possible to support it but the intended use would be to read/write data from these linearly so they don’t support them yet at least
In theory, it is not too hard to implement an immutable hash map based on Hash Array Mapped Tries. But it require a tree structure so you have to flat tree into a continues blob to fit it into BlobAsset or allocate multiple BlobAssets to represent tree structure. (LanguageExt.HashMap / LanguageExt.TrieMap)
I don’t understand your use case, but in my experience, Entity itself is kind of Map structure which similar to Map<Type[typeof(IComponentData)], IComponentData> or Map<int[TypeIndex], IComponentData>, so why don’t you just store your data into several IComponentData?
You could write your own naive “1st semester computer science” implementation on top of a list / array with a hash function and linear search on collision for the time being, and optimize from there.
If you are good with pointers UnsafeHashMap<TKey, TValue> and it’s internal pointer UnsafeHashMapData* m_Buffer.
Is a good point to store hashmap as Blob data.
UnsafeHashMapData has several pointers, as data would be immutable in blob memory, UnsafeHashMapData can be re-allocated continually, and be stored as blob data. when used just set UnsafeHashMap<TKey, TValue>.m_Buffer to the UnsafeHashMapData you stored.
I have got it working
First, you need to has internal access to unity.collections; Please refer to this:
Then this world work:
Code
unsafe public struct HashMapBlob
{
[Conditional("ENABLE_UNITY_COLLECTIONS_CHECKS")]
public static void CheckAlignment(this int alignment)
{
var zeroAlignment = alignment == 0;
var powTwoAlignment = ((alignment - 1) & alignment) == 0;
var validAlignment = (!zeroAlignment) && powTwoAlignment;
if (!validAlignment)
{
throw new ArgumentException($"Specified alignment must be non-zero positive power of two. Requested: {alignment}");
}
}
public static int Align(this int offset, int alignment)
{
CheckAlignment(alignment);
return (offset + (alignment - 1)) & -alignment;
}
public static readonly int k_HeaderSize = UnsafeUtility.SizeOf<HashMapBlob>().Align(JobsUtility.CacheLineSize);
unsafe internal static HashMapBlob* FromHashMapDataRaw<TKey, TValue>(UnsafeHashMapData* data, Allocator label)
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
{
UnsafeHashMapData.IsBlittableAndThrow<TKey, TValue>();
var keyCapacity = data->keyCapacity;
var bucketCapacityMask = data->bucketCapacityMask;
var bucketCapacity = bucketCapacityMask + 1;
int dataSize = UnsafeHashMapData.CalculateDataSize<TKey, TValue>(keyCapacity, bucketCapacity, out var keyOffset, out var nextOffset, out var bucketOffset);
int totalSize = k_HeaderSize + dataSize;
HashMapBlob* pBlob = (HashMapBlob*)UnsafeUtility.Malloc(totalSize, JobsUtility.CacheLineSize, label);
var pValueOut = (byte*)(pBlob) + k_HeaderSize;
var pKeysOut = pValueOut + keyOffset;
var pNextOut = pValueOut + nextOffset;
var pBucketsOut = pValueOut + bucketOffset;
UnsafeUtility.MemCpy(pValueOut, data->values, keyCapacity * UnsafeUtility.SizeOf<TValue>());
UnsafeUtility.MemCpy(pKeysOut, data->keys, keyCapacity * UnsafeUtility.SizeOf<TKey>());
UnsafeUtility.MemCpy(pNextOut, data->next, keyCapacity * UnsafeUtility.SizeOf<int>());
UnsafeUtility.MemCpy(pBucketsOut, data->buckets, bucketCapacity * UnsafeUtility.SizeOf<int>());
pBlob->m_TotalSize = totalSize;
pBlob->m_KeyOffset = keyOffset;
pBlob->m_NextOffset = nextOffset;
pBlob->m_BucketOffset = bucketOffset;
pBlob->m_keyCapacity = keyCapacity;
pBlob->m_bucketCapacityMask = bucketCapacityMask;
pBlob->m_allocatedIndexLength = math.min(data->allocatedIndexLength, data->keyCapacity);
pBlob->m_pBuffer = default;
return pBlob;
}
unsafe internal static HashMapBlob* FromHashMapRaw<TKey, TValue>(UnsafeHashMap<TKey, TValue> map, Allocator label)
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
=> FromHashMapDataRaw<TKey, TValue>(map.m_Buffer, label);
unsafe internal static HashMapBlob* FromHashMapRaw<TKey, TValue>(NativeHashMap<TKey, TValue> map, Allocator label)
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
=> FromHashMapDataRaw<TKey, TValue>(map.m_HashMapData.m_Buffer, label);
unsafe internal static HashMapBlob* FromMultiMapRaw<TKey, TValue>(UnsafeMultiHashMap<TKey, TValue> map, Allocator label)
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
=> FromHashMapDataRaw<TKey, TValue>(map.m_Buffer, label);
unsafe internal static HashMapBlob* FromMultiMapRaw<TKey, TValue>(NativeMultiHashMap<TKey, TValue> map, Allocator label)
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
=> FromHashMapDataRaw<TKey, TValue>(map.m_MultiHashMapData.m_Buffer, label);
unsafe internal static HashMapBlob* FromHasSetRaw<T>(UnsafeHashSet<T> set, Allocator label)
where T : unmanaged, IEquatable<T>
=> FromHashMapDataRaw<T, bool>(set.m_Data.m_Buffer, label);
unsafe internal static HashMapBlob* FromHasSetRaw<T>(NativeHashSet<T> map, Allocator label)
where T : unmanaged, IEquatable<T>
=> FromHashMapDataRaw<T, bool>(map.m_Data.m_HashMapData.m_Buffer, label);
public void BuildUnsafeHashMapData()
{
m_pBuffer.values = PThis + k_HeaderSize;
m_pBuffer.keys = m_pBuffer.values + m_KeyOffset;
m_pBuffer.next = m_pBuffer.values + m_NextOffset;
m_pBuffer.buckets = m_pBuffer.values + m_BucketOffset;
m_pBuffer.keyCapacity = m_keyCapacity;
m_pBuffer.bucketCapacityMask = m_bucketCapacityMask;
m_pBuffer.allocatedIndexLength = m_allocatedIndexLength;
for (int tls = 0; tls < JobsUtility.MaxJobThreadCount; ++tls) { m_pBuffer.firstFreeTLS[tls * UnsafeHashMapData.IntsPerCacheLine] = -1; }
}
unsafe internal static BlobAssetReference<HashMapBlob> FromHashMapData<TKey, TValue>(UnsafeHashMapData* data)
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
{
var pBlob = FromHashMapDataRaw<TKey, TValue>(data, Allocator.Temp);
var asset = BlobAssetReference<HashMapBlob>.Create(pBlob, pBlob->m_TotalSize);
asset.Value.BuildUnsafeHashMapData();
return asset;
}
unsafe public static BlobAssetReference<HashMapBlob> FromHashMap<TKey, TValue>(UnsafeHashMap<TKey, TValue> map)
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
=> FromHashMapData<TKey, TValue>(map.m_Buffer);
unsafe public static BlobAssetReference<HashMapBlob> FromHashMap<TKey, TValue>(NativeHashMap<TKey, TValue> map)
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
=> FromHashMapData<TKey, TValue>(map.m_HashMapData.m_Buffer);
unsafe public static BlobAssetReference<HashMapBlob> FromMultiMap<TKey, TValue>(UnsafeMultiHashMap<TKey, TValue> map)
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
=> FromHashMapData<TKey, TValue>(map.m_Buffer);
unsafe public static BlobAssetReference<HashMapBlob> FromMultiMap<TKey, TValue>(NativeMultiHashMap<TKey, TValue> map)
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
=> FromHashMapData<TKey, TValue>(map.m_MultiHashMapData.m_Buffer);
unsafe public static BlobAssetReference<HashMapBlob> FromHasSet<T>(UnsafeHashSet<T> set)
where T : unmanaged, IEquatable<T>
=> FromHashMapData<T, bool>(set.m_Data.m_Buffer);
unsafe public static BlobAssetReference<HashMapBlob> FromHasSet<T>(NativeHashSet<T> map)
where T : unmanaged, IEquatable<T>
=> FromHashMapData<T, bool>(map.m_Data.m_HashMapData.m_Buffer);
unsafe internal byte* PThis { get { fixed (void* pThis = &this) { return (byte*)pThis; } } }
unsafe internal UnsafeHashMapData* Buffer { get { fixed (UnsafeHashMapData* pBuf = &m_pBuffer) return pBuf; } }
int m_TotalSize;
int m_KeyOffset;
int m_NextOffset;
int m_BucketOffset;
internal int m_keyCapacity;
internal int m_bucketCapacityMask;
internal int m_allocatedIndexLength;
UnsafeHashMapData m_pBuffer;
unsafe public UnsafeHashMap<TKey, TValue> AsHashMap<TKey, TValue>()
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
=> new UnsafeHashMap<TKey, TValue>() { m_Buffer = Buffer };
unsafe public UnsafeMultiHashMap<TKey, TValue> AsMultiMap<TKey, TValue>()
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
=> new UnsafeMultiHashMap<TKey, TValue>() { m_Buffer = Buffer };
public UnsafeHashSet<T> AsHashSet<T>() where T : unmanaged, IEquatable<T>
=> new UnsafeHashSet<T>() { m_Data = AsHashMap<T, bool>() };
}
Works with *HashMap *MultiHashMap *HashSet
BuildUnsafeHashMapData() needs to be called whenever data is relocated, for example, move to BlobAssetStore.
Content is read-only, never add remove or clear the hashmap converted from the blob. Doing so will corrupt internal data.
This is not a correct way of implementing it. It will not work with serialized data. The whole point of blobs is to be relocatable…
The correct way to implement it is to build on top of BlobArray structures. Reusing UnsafeHashmap code is not possible since it uses pointers, but it it should be straightforward to copy & adjust some of the code from unsafehashmap. It should be much simpler than the full implementation since you only need read / lookup functionality & the ability to copy data from a NativeHashMap.
I am in fact rebuilding all “pointed” memory of UnsafeHashMapData as a contiguous memory block and recording all data array offsets. So it is a relocatable deep memcpy. when it is used as a *HasMap, UnsafeHashMapData is rebuilt by offsetting pointers inside of BlobAsset memory address. So it is working as long as it is read-only. When accessed from blob returning a different warping struct like “ReadonlyHashMap” with only read access would be better in this case, what I am doing is reusing UnsafeHashMap for simplicity.
I wrote a BlobHashMap half years ago. Using similar extension API like allocating blobArray, can be easily convert from/to C# dictionary. Also can store in byte[ ], so it’s a good way to implementing Monobehavior dictionary serialization.
Core part:
public struct BlobHashMap<TKey, TValue> where TKey : struct, IEquatable<TKey> where TValue : struct
{
[StructLayout(LayoutKind.Sequential)]
public struct Entry
{
public int next;
public TKey key;
public TValue value;
}
internal BlobArray<int> buckets;
internal BlobArray<Entry> data;
internal int halfPV;
public int Count
{
get { return data.Length; }
}
public ref TValue Get(in TKey _key)
{
if (buckets.Length == -1) throw new Exception();
if (halfPV <= 0 || Count <= 5)
{
for (int i = 0, c = Count; i < c; ++i)
{
ref var entry = ref data[i];
if (entry.key.Equals(_key))
{
return ref entry.value;
}
}
}
else
{
var bucketIndex = _key.GetHashCode() % halfPV;
bucketIndex = buckets[bucketIndex + halfPV];
while (bucketIndex != -1)
{
ref var entry = ref data[bucketIndex];
ref var key = ref entry.key;
if (key.Equals(_key))
{
return ref entry.value;
}
bucketIndex = entry.next;
}
}
throw new KeyNotFoundException();
}
public ref TValue Get(in string _key)
{
if (halfPV <= 0 || Count <= 5)
{
for (int i = 0, c = Count; i < c; ++i)
{
ref var entry = ref data[i];
if (entry.key.Equals(_key))
{
return ref entry.value;
}
}
}
else
{
var bucketIndex = _key.GetHashCode() % halfPV;
bucketIndex = buckets[bucketIndex + halfPV];
while (bucketIndex != -1)
{
ref var entry = ref data[bucketIndex];
if (entry.key.Equals(_key))
{
return ref entry.value;
}
bucketIndex = entry.next;
}
}
throw new KeyNotFoundException();
}
public bool ContainsKey(in TKey _key)
{
if (halfPV <= 0 || Count <= 5)
{
for (int i = 0, c = Count; i < c; ++i)
{
ref var entry = ref data[i];
if (entry.key.Equals(_key))
{
return true;
}
}
}
else
{
var bucketIndex = _key.GetHashCode() % halfPV;
bucketIndex = buckets[bucketIndex + halfPV];
while (bucketIndex != -1)
{
ref var entry = ref data[bucketIndex];
if (entry.key.Equals(_key))
{
return true;
}
bucketIndex = entry.next;
}
}
return false;
}
public bool ContainsKey(in string _key)
{
if (halfPV <= 0 || Count <= 5)
{
for (int i = 0, c = Count; i < c; ++i)
{
ref var entry = ref data[i];
if (entry.key.Equals(_key))
{
return true;
}
}
}
else
{
var bucketIndex = _key.GetHashCode() % halfPV;
bucketIndex = buckets[bucketIndex + halfPV];
while (bucketIndex != -1)
{
ref var entry = ref data[bucketIndex];
if (entry.key.Equals(_key))
{
return true;
}
bucketIndex = entry.next;
}
}
return false;
}
public bool TryGetValue(in TKey _key, out TValue _value)
{
if (halfPV <= 0 || Count <= 5)
{
for (int i = 0, c = Count; i < c; ++i)
{
ref var entry = ref data[i];
if (entry.key.Equals(_key))
{
_value = entry.value;
return true;
}
}
}
else
{
var bucketIndex = buckets[_key.GetHashCode() % halfPV + halfPV];
while (bucketIndex != -1)
{
ref var entry = ref data[bucketIndex];
if (entry.key.Equals(_key))
{
_value = entry.value;
return true;
}
bucketIndex = entry.next;
}
}
_value = default;
return false;
}
public bool TryGetValue(in string _key, out TValue _value)
{
if (halfPV <= 0 || Count <= 5)
{
for (int i = 0, c = Count; i < c; ++i)
{
ref var entry = ref data[i];
if (entry.key.Equals(_key))
{
_value = entry.value;
return true;
}
}
}
else
{
var bucketIndex = buckets[_key.GetHashCode() % halfPV + halfPV];
while (bucketIndex != -1)
{
ref var entry = ref data[bucketIndex];
if (entry.key.Equals(_key))
{
_value = entry.value;
return true;
}
bucketIndex = entry.next;
}
}
_value = default;
return false;
}
public void ForEach(BlobHashMapForEachCallback<TKey, TValue> _callback)
{
for (int i = 0, count = data.Length; i < count; ++i)
{
ref var entry = ref data[i];
_callback.Invoke(ref entry.key, ref entry.value);
}
}
public NativeArray<TKey> GetKeys(Allocator _allocator = Allocator.Temp)
{
var length = data.Length;
var array = new NativeArray<TKey>(length, _allocator, NativeArrayOptions.UninitializedMemory);
for (var i = 0; i < length; ++i)
{
ref var entry = ref data[i];
array[i] = entry.key;
}
return array;
}
}
Creation Part
public static class BlobHashMapExtensions
{
private static bool IsPrime(int n)
{
if (n < 2) return false;
for (var i = n - 1; i > 1; i--)
{
if (n % i == 0)
return false;
}
return true;
}
private static void InternalAllocateHashMap<TKey, TValue, TDataKey, TDataValue>(ref this BlobBuilder builder,
ref BlobHashMap<TKey, TValue> hashMap, Dictionary<TDataKey, TDataValue> value,
BlobElementConverter<TKey, TValue, TDataKey, TDataValue> converter)
where TKey : struct, IEquatable<TKey> where TValue : struct
{
var count = value.Count;
if (count == 0) return;
var pV = 2;
if (count > 2)
{
for (int i = count - 1; i >= 0; --i)
{
if (IsPrime(i))
{
pV = i;
break;
}
}
}
var bucketArray = builder.Allocate(ref hashMap.buckets, pV);
var dataArray = builder.Allocate(ref hashMap.data, count);
var halfPv = pV / 2;
hashMap.halfPV = halfPv;
for (int i = 0; i < pV; ++i)
{
bucketArray[i] = -1;
}
var entryIndex = 0;
foreach (var pair in value)
{
var bucketIndex = pair.Key.GetHashCode() % halfPv + halfPv;
dataArray[entryIndex] = new BlobHashMap<TKey, TValue>.Entry
{
next = -1
};
ref var a = ref dataArray[entryIndex];
converter(ref builder, ref a, pair);
if (bucketArray[bucketIndex] == -1)
{
bucketArray[bucketIndex] = entryIndex;
}
else
{
var tempIndex = bucketArray[bucketIndex];
while (dataArray[tempIndex].next != -1)
{
tempIndex = dataArray[tempIndex].next;
}
ref var v = ref dataArray[tempIndex];
v.next = entryIndex;
}
++entryIndex;
}
}
public static void DebugHashMap<TKey, TValue>(ref this BlobHashMap<TKey, TValue> _map)
where TKey : struct, IEquatable<TKey> where TValue : struct
{
_map.ForEach(((ref TKey _key, ref TValue _value) =>
{
UnityEngine.Debug.Log($"Key = {_key}, Value = {_value.ToString()}");
}));
}
public static void AllocateHashMap<TKey, TValue>(ref this BlobBuilder builder,
ref BlobHashMap<TKey, TValue> hashMap, Dictionary<TKey, TValue> value)
where TKey : struct, IEquatable<TKey> where TValue : struct
{
InternalAllocateHashMap(ref builder, ref hashMap, value,
(ref BlobBuilder _builder, ref BlobHashMap<TKey, TValue>.Entry _entry,
in KeyValuePair<TKey, TValue> _value) =>
{
_entry.key = _value.Key;
_entry.value = _value.Value;
});
}
public static void AllocateHashMap<TKey, TValue>(ref this BlobBuilder builder,
ref BlobHashMap<TKey, BlobArray<TValue>> hashMap, Dictionary<TKey, List<TValue>> value)
where TKey : struct, IEquatable<TKey> where TValue : struct
{
InternalAllocateHashMap(ref builder, ref hashMap, value,
(ref BlobBuilder _builder, ref BlobHashMap<TKey, BlobArray<TValue>>.Entry _entry,
in KeyValuePair<TKey, List<TValue>> _value) =>
{
_entry.key = _value.Key;
if (_value.Value != null && _value.Value.Count > 0)
{
_builder.AllocateArray(ref _entry.value, _value.Value);
}
});
}
public static void AllocateHashMap(ref this BlobBuilder builder,
ref BlobHashMap<BlobString, BlobString> hashMap, Dictionary<string, string> value)
{
InternalAllocateHashMap(ref builder, ref hashMap, value,
((ref BlobBuilder _builder, ref BlobHashMap<BlobString, BlobString>.Entry _entry,
in KeyValuePair<string, string> _value) =>
{
_builder.AllocateString(ref _entry.key, _value.Key);
_builder.AllocateString(ref _entry.value, _value.Value);
}));
}
public static void AllocateHashMap(ref this BlobBuilder builder,
ref BlobHashMap<BlobString, BlobArray<BlobString>> hashMap, Dictionary<string, List<string>> value)
{
InternalAllocateHashMap(ref builder, ref hashMap, value,
((ref BlobBuilder _builder, ref BlobHashMap<BlobString, BlobArray<BlobString>>.Entry _entry,
in KeyValuePair<string, List<string>> _value) =>
{
_builder.AllocateString(ref _entry.key, _value.Key);
var list = _value.Value;
if (list != null && list.Count > 0)
{
var array = _builder.Allocate(ref _entry.value, list.Count);
for (int i = 0; i < list.Count; ++i)
{
_builder.AllocateString(ref array[i], list[i]);
}
}
}));
}
public static void AllocateHashMap<TKey>(ref this BlobBuilder builder,
ref BlobHashMap<TKey, BlobString> hashMap, Dictionary<TKey, string> value)
where TKey : struct, IEquatable<TKey>
{
InternalAllocateHashMap(ref builder, ref hashMap, value,
((ref BlobBuilder _builder, ref BlobHashMap<TKey, BlobString>.Entry _entry,
in KeyValuePair<TKey, string> _value) =>
{
_entry.key = _value.Key;
_builder.AllocateString(ref _entry.value, _value.Value);
}));
}
public static void AllocateHashMap<TKey>(ref this BlobBuilder builder,
ref BlobHashMap<TKey, BlobArray<BlobString>> hashMap, Dictionary<TKey, List<string>> value)
where TKey : struct, IEquatable<TKey>
{
InternalAllocateHashMap(ref builder, ref hashMap, value,
((ref BlobBuilder _builder, ref BlobHashMap<TKey, BlobArray<BlobString>>.Entry _entry,
in KeyValuePair<TKey, List<string>> _value) =>
{
_entry.key = _value.Key;
var list = _value.Value;
if (list != null && list.Count > 0)
{
var array = _builder.Allocate(ref _entry.value, list.Count);
for (int i = 0; i < list.Count; ++i)
{
_builder.AllocateString(ref array[i], list[i]);
}
}
}));
}
public static void AllocateHashMap<TValue>(ref this BlobBuilder builder,
ref BlobHashMap<BlobString, TValue> hashMap, Dictionary<string, TValue> value)
where TValue : struct
{
InternalAllocateHashMap(ref builder, ref hashMap, value,
((ref BlobBuilder _builder, ref BlobHashMap<BlobString, TValue>.Entry _entry,
in KeyValuePair<string, TValue> _value) =>
{
_builder.AllocateString(ref _entry.key, _value.Key);
_entry.value = _value.Value;
}));
}
public static void AllocateHashMap<TValue>(ref this BlobBuilder builder,
ref BlobHashMap<BlobString, BlobArray<TValue>> hashMap, Dictionary<string, List<TValue>> value)
where TValue : struct
{
InternalAllocateHashMap(ref builder, ref hashMap, value,
((ref BlobBuilder _builder, ref BlobHashMap<BlobString,BlobArray<TValue>>.Entry _entry,
in KeyValuePair<string, List<TValue>> _value) =>
{
_builder.AllocateString(ref _entry.key, _value.Key);
if (_value.Value != null && _value.Value.Count > 0)
{
_builder.AllocateArray(ref _entry.value, _value.Value);
}
}));
}
public static void AllocateHashMap<TKey, TValue, TValueProxy>(ref this BlobBuilder builder,
ref BlobHashMap<TKey, TValue> hashMap, Dictionary<TKey, TValueProxy> value)
where TKey : struct, IEquatable<TKey>
where TValue : struct
where TValueProxy : IBlobProxy<TValue>
{
InternalAllocateHashMap(ref builder, ref hashMap, value,
((ref BlobBuilder _builder, ref BlobHashMap<TKey, TValue>.Entry _entry,
in KeyValuePair<TKey, TValueProxy> _value) =>
{
_entry.key = _value.Key;
_value.Value.Build(ref _builder, ref _entry.value);
}));
}
public static void AllocateHashMap<TKey, TValue, TValueProxy>(ref this BlobBuilder builder,
ref BlobHashMap<TKey, BlobArray<TValue>> hashMap, Dictionary<TKey, List<TValueProxy>> value)
where TKey : struct, IEquatable<TKey>
where TValue : struct
where TValueProxy : IBlobProxy<TValue>
{
InternalAllocateHashMap(ref builder, ref hashMap, value,
((ref BlobBuilder _builder, ref BlobHashMap<TKey, BlobArray<TValue>>.Entry _entry,
in KeyValuePair<TKey, List<TValueProxy>> _value) =>
{
_entry.key = _value.Key;
var list = _value.Value;
if (list != null && list.Count > 0)
{
var array = _builder.Allocate(ref _entry.value, list.Count);
for (int i = 0; i < list.Count; ++i)
{
list[i].Build(ref _builder, ref array[i]);
}
}
}));
}
public static void AllocateHashMap<TKey, TValue, TKeyProxy>(ref this BlobBuilder builder,
ref BlobHashMap<TKey, TValue> hashMap, Dictionary<TKeyProxy, TValue> value)
where TKey : struct, IEquatable<TKey>
where TValue : struct
where TKeyProxy : IBlobProxy<TKey>
{
InternalAllocateHashMap(ref builder, ref hashMap, value,
((ref BlobBuilder _builder, ref BlobHashMap<TKey, TValue>.Entry _entry,
in KeyValuePair<TKeyProxy, TValue> _value) =>
{
_value.Key.Build(ref _builder, ref _entry.key);
_entry.value = _value.Value;
}));
}
public static void AllocateHashMap<TKey, TValue, TKeyProxy>(ref this BlobBuilder builder,
ref BlobHashMap<TKey, BlobArray<TValue>> hashMap, Dictionary<TKeyProxy, List<TValue>> value)
where TKey : struct, IEquatable<TKey>
where TValue : struct
where TKeyProxy : IBlobProxy<TKey>
{
InternalAllocateHashMap(ref builder, ref hashMap, value,
((ref BlobBuilder _builder, ref BlobHashMap<TKey, BlobArray<TValue>>.Entry _entry,
in KeyValuePair<TKeyProxy, List<TValue>> _value) =>
{
_value.Key.Build(ref _builder, ref _entry.key);
var list = _value.Value;
if (list != null && list.Count > 0)
{
_builder.AllocateArray(ref _entry.value, list);
}
}));
}
public static void AllocateHashMap<TKey, TValue, TKeyProxy, TValueProxy>(ref this BlobBuilder builder,
ref BlobHashMap<TKey, TValue> hashMap, Dictionary<TKeyProxy, TValueProxy> value)
where TKey : struct, IEquatable<TKey>
where TValue : struct
where TKeyProxy : IBlobProxy<TKey>
where TValueProxy : IBlobProxy<TValue>
{
InternalAllocateHashMap(ref builder, ref hashMap, value,
((ref BlobBuilder _builder, ref BlobHashMap<TKey, TValue>.Entry _entry,
in KeyValuePair<TKeyProxy, TValueProxy> _value) =>
{
_value.Key.Build(ref _builder, ref _entry.key);
_value.Value.Build(ref _builder, ref _entry.value);
}));
}
public static void AllocateHashMap<TKey, TValue, TKeyProxy, TValueProxy>(ref this BlobBuilder builder,
ref BlobHashMap<TKey, BlobArray<TValue>> hashMap, Dictionary<TKeyProxy, List<TValueProxy>> value)
where TKey : struct, IEquatable<TKey>
where TValue : struct
where TKeyProxy : IBlobProxy<TKey>
where TValueProxy : IBlobProxy<TValue>
{
InternalAllocateHashMap(ref builder, ref hashMap, value,
((ref BlobBuilder _builder, ref BlobHashMap<TKey, BlobArray<TValue>>.Entry _entry,
in KeyValuePair<TKeyProxy, List<TValueProxy>> _value) =>
{
_value.Key.Build(ref _builder, ref _entry.key);
var list = _value.Value;
if (list != null && list.Count > 0)
{
var array = _builder.Allocate(ref _entry.value, list.Count);
for (int i = 0; i < list.Count; ++i)
{
list[i].Build(ref _builder, ref array[i]);
}
}
}));
}
public static void ConvertToDictionary<TKey, TValue>(ref this BlobHashMap<TKey, TValue> hashMap,
out Dictionary<TKey, TValue> result)
where TKey : struct, IEquatable<TKey> where TValue : struct
{
var temp = new Dictionary<TKey, TValue>();
hashMap.ForEach(((ref TKey _key, ref TValue _value) => { temp.Add(_key, _value); }));
result = temp;
}
public static void ConvertToDictionaryProxyKey<TKey, TValue, TKeyProxy>(
ref this BlobHashMap<TKey, TValue> hashMap,
out Dictionary<TKeyProxy, TValue> result)
where TKey : struct, IEquatable<TKey>
where TValue : struct
where TKeyProxy : IBlobAutoProxy<TKey>, new()
{
var temp = new Dictionary<TKeyProxy, TValue>();
hashMap.ForEach(((ref TKey _key, ref TValue _value) =>
{
var k = new TKeyProxy();
k.Revert(ref _key);
temp.Add(k, _value);
}));
result = temp;
}
public static void ConvertToDictionaryProxyValue<TKey, TValue, TValueProxy>(
ref this BlobHashMap<TKey, TValue> hashMap,
out Dictionary<TKey, TValueProxy> result)
where TKey : struct, IEquatable<TKey>
where TValue : struct
where TValueProxy : IBlobAutoProxy<TValue>, new()
{
var temp = new Dictionary<TKey, TValueProxy>();
hashMap.ForEach(((ref TKey _key, ref TValue _value) =>
{
var v = new TValueProxy();
v.Revert(ref _value);
temp.Add(_key, v);
}));
result = temp;
}
public static void ConvertToDictionaryProxyKeyValue<TKey, TValue, TKeyProxy, TValueProxy>(
ref this BlobHashMap<TKey, TValue> hashMap,
out Dictionary<TKeyProxy, TValueProxy> result)
where TKey : struct, IEquatable<TKey>
where TValue : struct
where TKeyProxy : IBlobAutoProxy<TKey>, new()
where TValueProxy : IBlobAutoProxy<TValue>, new()
{
var temp = new Dictionary<TKeyProxy, TValueProxy>();
hashMap.ForEach(((ref TKey _key, ref TValue _value) =>
{
var k = new TKeyProxy();
k.Revert(ref _key);
var v = new TValueProxy();
v.Revert(ref _value);
temp.Add(k, v);
}));
result = temp;
}
public static void ConvertToDictionary<TKey>(ref this BlobHashMap<TKey, BlobString> hashMap,
out Dictionary<TKey, string> result)
where TKey : struct, IEquatable<TKey>
{
var temp = new Dictionary<TKey, string>();
hashMap.ForEach(((ref TKey _key, ref BlobString _value) => { temp.Add(_key, _value.ToString()); }));
result = temp;
}
public static void ConvertToDictionary<TValue>(ref this BlobHashMap<BlobString, TValue> hashMap,
out Dictionary<string, TValue> result)
where TValue : struct
{
var temp = new Dictionary<string, TValue>();
hashMap.ForEach(((ref BlobString _key, ref TValue _value) => { temp.Add(_key.ToString(), _value); }));
result = temp;
}
public static void ConvertToDictionary(ref this BlobHashMap<BlobString, BlobString> hashMap,
out Dictionary<string, string> result)
{
var temp = new Dictionary<string, string>();
hashMap.ForEach(((ref BlobString _key, ref BlobString _value) =>
{
temp.Add(_key.ToString(), _value.ToString());
}));
result = temp;
}
}
Example :
var data = new Dictionary<TDataKey, TDataValue>();
for (var i = 0; i < _randomDataCount; ++i)
{
var pair = _randomData();
data[pair.Key] = pair.Value;
}
var builder = new BlobBuilder(Allocator.Temp);
try
{
ref var root = ref builder.ConstructRoot<BlobHashMap<TKey, TValue>>();
builder.AllocateHashMap(ref root, data);
var result = builder.CreateBlobAssetReference<BlobHashMap<TKey, TValue>>(Allocator.Temp);
MemoryBinaryReader reader;
MemoryBinaryWriter writer;
unsafe
{
writer = new MemoryBinaryWriter();
writer.Write(result);
reader = new MemoryBinaryReader(writer.Data);
}
try
{
_assertion(reader, data);
}
finally
{
writer.Dispose();
reader.Dispose();
}
}
finally
{
builder.Dispose();
}
That looks like a solid implementation in line with what I would expect.
Creation via NativeHashMap seems useful…
I got what it means by “It will not work with serialized data”. BlobAssetReference can only serialize and deserialize fixed-sized structs. Those extra data after the struct memory location will be lost when serialized.
I got a further question, for a blob hashmap it needs serial BlobArray for values, keys, nexts, and buckets.
Question 1. In this case, Can these blob arrays be nested inside of a BlobAssetReference?
Question 2. Can I assure these BlobArrays are allocated contiguously?
I think I can still construct a UnsafeHashMapData from separate BlobArray using pointers. And use existing UnsafeHashMapData API to build new ReadonlyHashMap/Set/Multimap
Like these
/// <summary>
/// Readonly, Key<=>Value 1:1
/// </summary>
public struct BlobHashMap<TKey, TValue>
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
{
internal UnsafeHashMapData Buffer;//Not using pointer as it is immutable
internal BlobHashMap(BlobAssetReference<HashMapDataBlob> blob) { Buffer = blob.Value.Buffer; }
public bool IsEmpty { get { unsafe { fixed (UnsafeHashMapData* m_Buffer = &Buffer) { return UnsafeHashMapData.IsEmpty(m_Buffer); } } } }
public int Count()
{
if (Buffer.allocatedIndexLength <= 0) return 0;
unsafe { fixed (UnsafeHashMapData* m_Buffer = &Buffer) return UnsafeHashMapData.GetCount(m_Buffer); }
}
public bool TryGetValue(TKey key, out TValue item)
{
NativeMultiHashMapIterator<TKey> tempIt;
unsafe { fixed (UnsafeHashMapData* m_Buffer = &Buffer) return UnsafeHashMapBase<TKey, TValue>.TryGetFirstValueAtomic(m_Buffer, key, out item, out tempIt); }
}
public bool ContainsKey(TKey key)
{
unsafe
{
fixed (UnsafeHashMapData* m_Buffer = &Buffer)
return UnsafeHashMapBase<TKey, TValue>.TryGetFirstValueAtomic(m_Buffer, key, out var tempValue, out var tempIt);
}
}
public TValue this[TKey key]
{
get
{
TValue res;
TryGetValue(key, out res);
return res;
}
}
public NativeArray<TKey> GetKeyArray(Allocator allocator)
{
unsafe
{
fixed (UnsafeHashMapData* m_Buffer = &Buffer)
{
var result = new NativeArray<TKey>(UnsafeHashMapData.GetCount(m_Buffer), allocator, NativeArrayOptions.UninitializedMemory);
UnsafeHashMapData.GetKeyArray(m_Buffer, result);
return result;
}
}
}
public NativeArray<TValue> GetValueArray(Allocator allocator)
{
unsafe
{
fixed (UnsafeHashMapData* m_Buffer = &Buffer)
{
var result = new NativeArray<TValue>(UnsafeHashMapData.GetCount(m_Buffer), allocator, NativeArrayOptions.UninitializedMemory);
UnsafeHashMapData.GetValueArray(m_Buffer, result);
return result;
}
}
}
public NativeKeyValueArrays<TKey, TValue> GetKeyValueArrays(Allocator allocator)
{
unsafe
{
fixed (UnsafeHashMapData* m_Buffer = &Buffer)
{
var result = new NativeKeyValueArrays<TKey, TValue>(UnsafeHashMapData.GetCount(m_Buffer), allocator, NativeArrayOptions.UninitializedMemory);
UnsafeHashMapData.GetKeyValueArrays(m_Buffer, result);
return result;
}
}
}
}
/// <summary>
/// Readonly, Key<=>Value 1:n
/// </summary>
public struct BlobMultimap<TKey, TValue>
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
{
internal UnsafeHashMapData Buffer;
internal BlobMultimap(BlobAssetReference<HashMapDataBlob> blob) { Buffer = blob.Value.Buffer; }
public bool IsEmpty { get { unsafe { fixed (UnsafeHashMapData* m_Buffer = &Buffer) { return UnsafeHashMapData.IsEmpty(m_Buffer); } } } }
public int Count()
{
if (Buffer.allocatedIndexLength <= 0) return 0;
unsafe { fixed (UnsafeHashMapData* m_Buffer = &Buffer) return UnsafeHashMapData.GetCount(m_Buffer); }
}
public bool TryGetFirstValue(TKey key, out TValue item, out NativeMultiHashMapIterator<TKey> it)
{
unsafe { fixed (UnsafeHashMapData* m_Buffer = &Buffer) return UnsafeHashMapBase<TKey, TValue>.TryGetFirstValueAtomic(m_Buffer, key, out item, out it); }
}
public int CountValuesForKey(TKey key)
{
if (!TryGetFirstValue(key, out var value, out var iterator))
{
return 0;
}
var count = 1;
while (TryGetNextValue(out value, ref iterator))
{
count++;
}
return count;
}
public bool TryGetNextValue(out TValue item, ref NativeMultiHashMapIterator<TKey> it)
{ unsafe { fixed (UnsafeHashMapData* m_Buffer = &Buffer) return UnsafeHashMapBase<TKey, TValue>.TryGetNextValueAtomic(m_Buffer, out item, ref it); } }
public bool ContainsKey(TKey key)
{ unsafe { fixed (UnsafeHashMapData* m_Buffer = &Buffer) return UnsafeHashMapBase<TKey, TValue>.TryGetFirstValueAtomic(m_Buffer, key, out var tempValue, out var tempIt); } }
public NativeArray<TKey> GetKeyArray(Allocator allocator)
{
unsafe
{
fixed (UnsafeHashMapData* m_Buffer = &Buffer)
{
var result = new NativeArray<TKey>(UnsafeHashMapData.GetCount(m_Buffer), allocator, NativeArrayOptions.UninitializedMemory);
UnsafeHashMapData.GetKeyArray(m_Buffer, result);
return result;
}
}
}
public NativeArray<TValue> GetValueArray(Allocator allocator)
{
unsafe
{
fixed (UnsafeHashMapData* m_Buffer = &Buffer)
{
var result = new NativeArray<TValue>(UnsafeHashMapData.GetCount(m_Buffer), allocator, NativeArrayOptions.UninitializedMemory);
UnsafeHashMapData.GetValueArray(m_Buffer, result);
return result;
}
}
}
public NativeKeyValueArrays<TKey, TValue> GetKeyValueArrays(Allocator allocator)
{
unsafe
{
fixed (UnsafeHashMapData* m_Buffer = &Buffer)
{
var result = new NativeKeyValueArrays<TKey, TValue>(UnsafeHashMapData.GetCount(m_Buffer), allocator, NativeArrayOptions.UninitializedMemory);
UnsafeHashMapData.GetKeyValueArrays(m_Buffer, result);
return result;
}
}
}
}
/// <summary>
/// Readonly, Element is unique
/// </summary>
public unsafe struct BlobHashSet<T>
where T : unmanaged, IEquatable<T>
{
internal UnsafeHashMapData Buffer;
internal BlobHashSet(BlobAssetReference<HashMapDataBlob> blob) { Buffer = blob.Value.Buffer; }
public bool IsEmpty { get { unsafe { fixed (UnsafeHashMapData* m_Buffer = &Buffer) { return UnsafeHashMapData.IsEmpty(m_Buffer); } } } }
public int Count()
{
if (Buffer.allocatedIndexLength <= 0) return 0;
unsafe { fixed (UnsafeHashMapData* m_Buffer = &Buffer) return UnsafeHashMapData.GetCount(m_Buffer); }
}
public bool Contains(T i
I got this BlobArray version working.
Still. you need to has internal access to Unity.Collections; Please refer to this:
BlobArray version Blob HashMap
HashMapDataBlob
unsafe public struct HashMapDataBlob<TKey, TValue>
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
{
internal int m_count;
internal int m_bucketCapacityMask;
public BlobArray<TKey> keys;
public BlobArray<TValue> values;
public BlobArray<int> buckets;
public BlobArray<int> next;
unsafe internal static BlobAssetReference<HashMapDataBlob<TKey, TValue>> FromHashMapData(UnsafeHashMapData* data, Allocator allocator = Allocator.Persistent)
{
UnsafeHashMapData.IsBlittableAndThrow<TKey, TValue>();
var pairCount = UnsafeHashMapData.GetCount(data);
var bucketCapacityMask = data->bucketCapacityMask;
var bucketCapacity = bucketCapacityMask + 1;
var builder = new BlobBuilder(Allocator.Temp);
ref var root = ref builder.ConstructRoot<HashMapDataBlob<TKey, TValue>>();
root.m_count = pairCount;
root.m_bucketCapacityMask = bucketCapacityMask;
var valueBuilder = builder.Allocate(ref root.values, pairCount);
var keyBuilder = builder.Allocate(ref root.keys, pairCount);
var nextBuilder = builder.Allocate(ref root.next, pairCount);
var bucketBuilder = builder.Allocate(ref root.buckets, bucketCapacity);
UnsafeUtility.MemSet(nextBuilder.GetUnsafePtr(), 0xff, pairCount * sizeof(int));
UnsafeUtility.MemSet(bucketBuilder.GetUnsafePtr(), 0xff, bucketCapacity * sizeof(int));
int* bucketsIn = (int*)data->buckets;
int* nextsIn = (int*)data->next;
TKey* keysIn = (TKey*)data->keys;
TValue* valueIn = (TValue*)data->values;
//Rebuild HashMap,
//1. remove all gaps
//2. order by buckets index(hash)
for (int bktId = 0, pairId = 0; bktId < bucketCapacity; bktId++)
{
var entry = bucketsIn[bktId];
if (entry >= 0)
{
Assert.IsTrue((entry < (data->keyCapacity)));
Assert.IsTrue((pairId < pairCount));
bucketBuilder[bktId] = pairId;
keyBuilder[pairId] = keysIn[entry];
valueBuilder[pairId] = valueIn[entry];
pairId++;
entry = nextsIn[entry];
while (entry >= 0)
{
Assert.IsTrue((entry < (data->keyCapacity)));
Assert.IsTrue((pairId < pairCount));
keyBuilder[pairId] = keysIn[entry];
valueBuilder[pairId] = valueIn[entry];
nextBuilder[pairId - 1] = pairId;
pairId++;
entry = nextsIn[entry];
}
}
}
return builder.CreateBlobAssetReference<HashMapDataBlob<TKey, TValue>>(allocator);
}
unsafe internal UnsafeHashMapData Buffer
{
get
{
var buffer = s_Neg1;
buffer.values = (byte*)values.GetUnsafePtr();
buffer.keys = (byte*)keys.GetUnsafePtr();
buffer.next = (byte*)next.GetUnsafePtr();
buffer.buckets = (byte*)buckets.GetUnsafePtr();
buffer.keyCapacity = m_count;
buffer.bucketCapacityMask = m_bucketCapacityMask;
buffer.allocatedIndexLength = m_count;
return buffer;
}
}
static readonly UnsafeHashMapData s_Neg1 = CreateNeg1();
unsafe static UnsafeHashMapData CreateNeg1()
{
var data = new UnsafeHashMapData();
UnsafeUtility.MemSet(&data, 0xff, UnsafeUtility.SizeOf<UnsafeHashMapData>());
return data;
}
}
Conversion extension
HashMapDataBlobExt
unsafe public static class HashMapDataBlobExt
{
unsafe public static BlobAssetReference<HashMapDataBlob<T, bool>> CreateBlobAsset<T>(this UnsafeHashSet<T> set, Allocator allocator = Allocator.Persistent)
where T : unmanaged, IEquatable<T>
=> HashMapDataBlob<T, bool>.FromHashMapData(set.m_Data.m_Buffer, allocator);
unsafe public static BlobAssetReference<HashMapDataBlob<T, bool>> ConvertToBlob<T>(this NativeHashSet<T> set, Allocator allocator = Allocator.Persistent)
where T : unmanaged, IEquatable<T>
=> HashMapDataBlob<T, bool>.FromHashMapData(set.m_Data.m_HashMapData.m_Buffer, allocator);
unsafe public static BlobAssetReference<HashMapDataBlob<TKey, TValue>> CreateBlobAsset<TKey, TValue>(this UnsafeHashMap<TKey, TValue> map, Allocator allocator = Allocator.Persistent)
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
=> HashMapDataBlob<TKey, TValue>.FromHashMapData(map.m_Buffer, allocator);
unsafe public static BlobAssetReference<HashMapDataBlob<TKey, TValue>> CreateBlobAsset<TKey, TValue>(this NativeHashMap<TKey, TValue> map, Allocator allocator = Allocator.Persistent)
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
=> HashMapDataBlob<TKey, TValue>.FromHashMapData(map.m_HashMapData.m_Buffer, allocator);
unsafe public static BlobAssetReference<HashMapDataBlob<TKey, TValue>> CreateBlobAsset<TKey, TValue>(this UnsafeMultiHashMap<TKey, TValue> map, Allocator allocator = Allocator.Persistent)
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
=> HashMapDataBlob<TKey, TValue>.FromHashMapData(map.m_Buffer, allocator);
unsafe public static BlobAssetReference<HashMapDataBlob<TKey, TValue>> CreateBlobAsset<TKey, TValue>(this NativeMultiHashMap<TKey, TValue> map, Allocator allocator = Allocator.Persistent)
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
=> HashMapDataBlob<TKey, TValue>.FromHashMapData(map.m_MultiHashMapData.m_Buffer, allocator);
public static BlobHashSet<T> AsReadonlyHashSet<T>(this BlobAssetReference<HashMapDataBlob<T, bool>> blob) where T : unmanaged, IEquatable<T>
=> new BlobHashSet<T>(blob);
public static BlobHashMap<TKey, TValue> AsReadonlyHashMap<TKey, TValue>(this BlobAssetReference<HashMapDataBlob<TKey, TValue>> blob)
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
=> new BlobHashMap<TKey, TValue>(blob);
public static BlobMultimap<TKey, TValue> AsReadonlyMultiMap<TKey, TValue>(this BlobAssetReference<HashMapDataBlob<TKey, TValue>> blob)
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged => new BlobMultimap<TKey, TValue>(blob);
}
And Readonly accessors
BlobHashMap,BlobMultimap,BlobHashSet
/// <summary>
/// Readonly, Key<=>Value 1:1
/// </summary>
public struct BlobHashMap<TKey, TValue>
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
{
internal UnsafeHashMapData Buffer;
internal BlobHashMap(BlobAssetReference<HashMapDataBlob<TKey, TValue>> blob) { Buffer = blob.Value.Buffer; }
internal unsafe UnsafeHashMapData* pBuffer { get { fixed (UnsafeHashMapData* m_Buffer = &Buffer) return m_Buffer; } }
public bool IsEmpty => Buffer.allocatedIndexLength <= 0;
//allocatedIndexLength is valid Because data was rebuilt odered and compact
public int Count => Buffer.allocatedIndexLength;
unsafe public bool TryGetValue(TKey key, out TValue item)
=> UnsafeHashMapBase<TKey, TValue>.TryGetFirstValueAtomic(pBuffer, key, out item, out _);
unsafe public bool ContainsKey(TKey key)
=> UnsafeHashMapBase<TKey, TValue>.TryGetFirstValueAtomic(pBuffer, key, out _, out _);
public TValue this[TKey key] { get { TryGetValue(key, out var res); return res; } }
public NativeArray<TKey> GetKeyArray(Allocator allocator)
{
var result = new NativeArray<TKey>(Buffer.allocatedIndexLength, allocator, NativeArrayOptions.UninitializedMemory);
unsafe { UnsafeUtility.MemCpy(result.GetUnsafePtr(), Buffer.keys, Buffer.allocatedIndexLength * UnsafeUtility.SizeOf<TKey>()); }
return result;
}
public NativeArray<TValue> GetValueArray(Allocator allocator)
{
var result = new NativeArray<TValue>(Buffer.allocatedIndexLength, allocator, NativeArrayOptions.UninitializedMemory);
unsafe { UnsafeUtility.MemCpy(result.GetUnsafePtr(), Buffer.values, Buffer.allocatedIndexLength * UnsafeUtility.SizeOf<TValue>()); }
return result;
}
public NativeKeyValueArrays<TKey, TValue> GetKeyValueArrays(Allocator allocator)
{
var result = new NativeKeyValueArrays<TKey, TValue>(Buffer.allocatedIndexLength, allocator, NativeArrayOptions.UninitializedMemory);
unsafe
{
UnsafeUtility.MemCpy(result.Keys.GetUnsafePtr(), Buffer.keys, Buffer.allocatedIndexLength * UnsafeUtility.SizeOf<TKey>());
UnsafeUtility.MemCpy(result.Values.GetUnsafePtr(), Buffer.values, Buffer.allocatedIndexLength * UnsafeUtility.SizeOf<TValue>());
}
return result;
}
}
/// <summary>
/// Readonly, Key<=>Value 1:n
/// </summary>
public struct BlobMultimap<TKey, TValue>
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
{
internal UnsafeHashMapData Buffer;
internal BlobMultimap(BlobAssetReference<HashMapDataBlob<TKey, TValue>> blob) { Buffer = blob.Value.Buffer; }
internal unsafe UnsafeHashMapData* pBuffer { get { fixed (UnsafeHashMapData* m_Buffer = &Buffer) return m_Buffer; } }
public bool IsEmpty => Buffer.allocatedIndexLength <= 0;
//allocatedIndexLength is valid Because data was rebuilt odered and compact
public int Count => Buffer.allocatedIndexLength;
unsafe public int CountValuesForKey(TKey key)
{
//this is valid Because data was rebuilt odered and compact
int* buckets = (int*)Buffer.buckets;
int bucketId = key.GetHashCode() & Buffer.bucketCapacityMask;
var start = buckets[bucketId];
var end = bucketId >= Buffer.bucketCapacityMask ? Buffer.allocatedIndexLength : buckets[bucketId + 1];
return end - start;
}
unsafe public bool TryGetFirstValue(TKey key, out TValue item, out NativeMultiHashMapIterator<TKey> it)
=> UnsafeHashMapBase<TKey, TValue>.TryGetFirstValueAtomic(pBuffer, key, out item, out it);
unsafe public bool TryGetNextValue(out TValue item, ref NativeMultiHashMapIterator<TKey> it)
=> UnsafeHashMapBase<TKey, TValue>.TryGetNextValueAtomic(pBuffer, out item, ref it);
unsafe public bool ContainsKey(TKey key) => UnsafeHashMapBase<TKey, TValue>.TryGetFirstValueAtomic(pBuffer, key, out _, out _);
public NativeArray<TKey> GetKeyArray(Allocator allocator)
{
var result = new NativeArray<TKey>(Buffer.allocatedIndexLength, allocator, NativeArrayOptions.UninitializedMemory);
unsafe { UnsafeUtility.MemCpy(result.GetUnsafePtr(), Buffer.keys, Buffer.allocatedIndexLength * UnsafeUtility.SizeOf<TKey>()); }
return result;
}
public NativeArray<TValue> GetValueArray(Allocator allocator)
{
var result = new NativeArray<TValue>(Buffer.allocatedIndexLength, allocator, NativeArrayOptions.UninitializedMemory);
unsafe { UnsafeUtility.MemCpy(result.GetUnsafePtr(), Buffer.values, Buffer.allocatedIndexLength * UnsafeUtility.SizeOf<TValue>()); }
return result;
}
public NativeKeyValueArrays<TKey, TValue> GetKeyValueArrays(Allocator allocator)
{
var result = new NativeKeyValueArrays<TKey, TValue>(Buffer.allocatedIndexLength, allocator, NativeArrayOptions.UninitializedMemory);
unsafe
{
UnsafeUtility.MemCpy(result.Keys.GetUnsafePtr(), Buffer.keys, Buffer.allocatedIndexLength * UnsafeUtility.SizeOf<TKey>());
UnsafeUtility.MemCpy(result.Values.GetUnsafePtr(), Buffer.values, Buffer.allocatedIndexLength * UnsafeUtility.SizeOf<TValue>());
}
return result;
}
}
/// <summary>
/// Readonly, Element is unique
/// </summary>
public unsafe struct BlobHashSet<T>
where T : unmanaged, IEquatable<T>
{
internal UnsafeHashMapData Buffer;
internal BlobHashSet(BlobAssetReference<HashMapDataBlob<T, bool>> blob) { Buffer = blob.Value.Buffer; }
internal unsafe UnsafeHashMapData* pBuffer { get { fixed (UnsafeHashMapData* m_Buffer = &Buffer) return m_Buffer; } }
public bool IsEmpty => Buffer.allocatedIndexLength <= 0;
//allocatedIndexLength is valid Because data was rebuilt odered and compact
public int Count => Buffer.allocatedIndexLength;
unsafe public bool Contains(T item) => UnsafeHashMapBase<T, bool>.TryGetFirstValueAtomic(pBuffer, item, out _, out _);
public NativeArray<T> ToNativeArray(Allocator allocator)
{
var result = new NativeArray<T>(Buffer.allocatedIndexLength, allocator, NativeArrayOptions.UninitializedMemory);
unsafe { UnsafeUtility.MemCpy(result.GetUnsafePtr(), Buffer.keys, Buffer.allocatedIndexLength * UnsafeUtility.SizeOf<T>()); }
return result;
}
}
Yes. BlobArray & BlobPtr can be nested inside each other.
This is also a correct way of implementing it.
The question is if the copying into the struct will result in a performance loss compared to having methods that work against Blob Array etc directly similar to what Thermos did.
I am not sure. It is possible burst will optimise it away or not. It is worth making a performance test for and comparing TryGetValue performance of both approaches. Overall the implementation that Thermos posted is quite clean I think.
One extra thing to note, the NativeHashMap implementation are optimised for parallel add / remove etc.
If the constraint is that building the hashtable can be slow and is done in batch. And only trygetvalue performance matters other hashtable implementations may be faster / better choices.
Once everything is known upfront you could for example make a hashtable that gurantees that the hash points to the key directly and no probing is necessary. eg. could directly do the lookup and not have any code following the probe. This could make lookup much faster & build time slower. Eg. change a hash modulator / key size until it fits the requirement.
@Thermos :
This line in your hashtable is very likely killing perf.
var bucketIndex = buckets[_key.GetHashCode() % halfPV + halfPV];
In our unsafehashmap we used & operator to mask the hash code. % operator is generally much more expensive than * + operators on ints across most platforms by often a magnitude of latency difference.
I think putting some work into precalculating an & mask value + offset, would probably get you significant wins. I assume that is part why you have to have a specialized innerloop for small amounts of keys. It would be worth checking if that can be made unnecessary simply optimising the lookup.
Thanks for the tips. Actually…I only use this BlobHashMap and outdated blob asset code(Which I copied from ECS 0.3) in our old project, which only tries to solve dictionary serialization and get a faster load time in Monobehavior & ScriptableObject world. Like the screenshot below, editing dictionary data and store into blob data(byte[ ]).
In our new DOTS based project we are working on a new data editing tool, it will map all keys into indices when build the final blob data, so we only need BlobArray, that also gives us a much faster access by using array & index.
But still, would like to see an official BlobHashMap support.
If you’re going to go to that level, there’s Fibonacci hashing, which helps prevent collisions as well as being fast to calculate: https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ .
Oh Yes! Phi could generate the most Irrational(None-Repeating pattern) Irrational Number. I’ll give it a try.
Thanks for sharing! There’s some missing stuff in your code, could you share the full relative code? I really need a BlobHashMap.
Sure. If you are using older version of unity.collection, you need to replace all UnsafeUtility.AsRef back to UnsafeUtilityEx.AsRef.
Also, if your project is ECS based, you could replace BlobControl.cs with latest blob asset code in ECS package.
6507070–732961–blob_ext.zip (24.3 KB)