[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

Prokopec, 2018 - Google Patents

Cache-tries: concurrent lock-free hash tries with constant-time operations

Prokopec, 2018

View PDF
Document ID
14173290794330101472
Author
Prokopec A
Publication year
Publication venue
Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

External Links

Snippet

Concurrent non-blocking hash tries have good cache locality, and horizontally scalable operations. However, operations on most existing concurrent hash tries run in O (log n) time. In this paper, we show that the concurrent hash trie operations can run in expected constant …
Continue reading at aleksandar-prokopec.com (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023—Free address space management
    • G06F12/0253—Garbage collection, i.e. reclamation of unreferenced memory
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30312—Storage and indexing structures; Management thereof
    • G06F17/30321—Indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G06F9/46—Multiprogramming arrangements
    • G06F9/52—Programme synchronisation; Mutual exclusion, e.g. by means of semaphores; Contention for resources among tasks
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30067—File systems; File servers
    • G06F17/30129—Details of further file system functionalities
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30345—Update requests
    • G06F17/30348—Concurrency control
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0806—Multiuser, multiprocessor or multiprocessing cache systems
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformations of program code
    • G06F8/41—Compilation
    • G06F8/44—Encoding
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Error detection; Error correction; Monitoring responding to the occurence of a fault, e.g. fault tolerance
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/70—Software maintenance or management
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F2201/00—Indexing scheme relating to error detection, to error correction, and to monitoring
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity

Similar Documents

Publication Publication Date Title
Kumar et al. Graphone: A data store for real-time analytics on evolving graphs
Prokopec Cache-tries: concurrent lock-free hash tries with constant-time operations
Wang et al. Building a bw-tree takes more than just buzz words
Howley et al. A non-blocking internal binary search tree
US7953778B2 (en) Efficient support of consistent cyclic search with read-copy update and parallel updates
US7987214B2 (en) Determining the address range of a subtree of a linearized tree
Nasre et al. Morph algorithms on GPUs
Bender et al. Concurrent cache-oblivious B-trees
Jordan et al. A specialized B-tree for concurrent datalog evaluation
US20110264870A1 (en) Using region status array to determine write barrier actions
Feldman et al. A wait-free multi-word compare-and-swap operation
Basin et al. Kiwi: A key-value map for scalable real-time analytics
Besta et al. Accelerating irregular computations with hardware transactional memory and active messages
Mathew et al. HydraList: A scalable in-memory index using asynchronous updates and partial replication
Moscovici et al. A gpu-friendly skiplist algorithm
Basin et al. KiWi: A key-value map for scalable real-time analytics
Pellegrini et al. Transparent and efficient shared-state management for optimistic simulations on multi-core machines
Burtscher et al. A high-quality and fast maximal independent set implementation for gpus
Islam et al. Dgap: Efficient dynamic graph analysis on persistent memory
Wang et al. Circ-Tree: A B+-Tree variant with circular design for persistent memory
JP4126843B2 (en) Data management method and apparatus, and recording medium storing data management program
Wang et al. The concurrent learned indexes for multicore data storage
Chowdhury et al. A scalable recoverable skip list for persistent memory
Peng et al. SLIMFAST: Reducing metadata redundancy in sound and complete dynamic data race detection
Tripp et al. FRC: a high-performance concurrent parallel deferred reference counter for C++