SYCLHashBackend.h File Reference

(bba9247 (Tue Jul 28 21:42:19 2026 -0700))

SYCL implementation of DeviceHashBackend (open addressing, in-tree). More...

#include <algorithm>
#include <cstdint>
#include <memory>
#include <sycl/sycl.hpp>
#include <vector>
#include "open3d/core/BlockCopyDispatch.h"
#include "open3d/core/MemoryManager.h"
#include "open3d/core/SYCLContext.h"
#include "open3d/core/hashmap/DeviceHashBackend.h"
#include "open3d/core/hashmap/Dispatch.h"
#include "open3d/core/hashmap/SYCL/SYCLHashBackendBufferAccessor.h"
#include "open3d/utility/Logging.h"

Go to the source code of this file.

Data Structures
struct	open3d::core::SYCLHashDeviceLookup< Key, Hash, Eq >
	Read-only table view for device kernels (see file header). More...
class	open3d::core::SYCLHashBackend< Key, Hash, Eq >
	DeviceHashBackend for SYCL devices (algorithm in file header). More...

Namespaces
namespace	open3d
namespace	open3d::core

Enumerations
enum	open3d::core::HashSlotState : uint32_t { open3d::core::kSlotEmpty = 0 , open3d::core::kSlotOccupied = 1 , open3d::core::kSlotDeleted = 2 }

Detailed Description

SYCL implementation of DeviceHashBackend (open addressing, in-tree).

Open3D's tensor HashMap and HashSet share one backend API on CPU (TBB), CUDA (stdgpu default, slab optional), and SYCL (this file). See also hashmap/SYCL_DESIGN.md for a short overview; this file header is the maintainer reference.

Role in the stack

• Keys are MiniVec<int, dim> with dim 1–6; keys and values live in HashBackendBuffer, not inside the probe table.
• Each occupied hash slot stores a buf_index into those buffers (unique-key map, not a multimap).
• Capacity growth is owned by HashMap::Reserve / HashSet::Reserve (export active entries → free backend → allocate → re-insert). This backend's SYCLHashBackend::Reserve() override is a no-op.

Data structure

Component	Description
Probing	Open addressing, linear probing, power-of-two bucket count
Index	(home + i) & (bucket_count - 1)
Slot (64-bit)	28-bit fingerprint | 4-bit state | 32-bit

buf_index (see PackSlot) | | States | EMPTY (0), OCCUPIED, DELETED (tombstone); EMPTY=0 ⇒ zero USM is empty | | HashMix | MurmurHash3 fmix64 on FNV-1a before mask; fingerprint skips most false key gathers |

Concurrency and operations

Insert (wait-free)

• Linear probe; reuse first DELETED slot seen when claiming EMPTY.
• Allocate one buffer element, write key/values, device seq_cst fence, then a single CAS EMPTY/DELETED → OCCUPIED (no lock spin — on Intel Xe, a waiting subgroup lane can hang the device).
• Duplicate-key races: loser gets masks=false and DeviceFree's its unused buffer slot ⇒ returned buf_indices are valid gather indices but not necessarily dense in [0, Size()) (see HashMap user docs).

Find / Erase

• Same probe; EMPTY ends the chain.
• Erase: CAS OCCUPIED → DELETED, free buffer slot; occupied_count_ decremented.
• non_empty_count_ tracks occupied + deleted (tombstone pressure).

GetActiveIndices

• Work-group exclusive scan + one global fetch_add per group (not one atomic per slot).

SYCLHashDeviceLookup

• Immutable snapshot for device kernels (Find uses plain loads, no atomics).
• Do not mutate the table while a lookup view is in use.

Compared to CUDA backends

Aspect	CUDA default (stdgpu)	SYCL (this file)
Dependency	Third-party stdgpu	None (in-tree)
Probing	Library-defined	Linear + stored fingerprint
In-kernel find	map.find(key)	SYCLHashDeviceLookup::Find(key)

Callers that treat buf_indices as dense row ids (e.g. voxel aggregation) must remap via unique insert slots (masks==true) or HashMap::GetActiveIndices(). Uses that only need masks or active-index lists are unchanged.

Related files

• SYCL/SYCLHashBackendBufferAccessor.h — USM key/value buffer access
• SYCL/CreateSYCLHashBackend.cpp — factory / dtype dispatch