Fast, Dynamically-Sized Concurrent Hash Table View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2015-08-27

AUTHORS

J. Barnat , P. Ročkai , V. Štill , J. Weiser

ABSTRACT

We present a new design and a C++ implementation of a high-performance, cache-efficient hash table suitable for use in implementation of parallel programs in shared memory. Among the main design criteria were the ability to efficiently use variable-length keys, dynamic table resizing to accommodate data sets of unpredictable size and fully concurrent read-write access.We show that the design is correct with respect to data races, both through a high-level argument, as well as by using a model checker to prove crucial safety properties of the actual implementation. Finally, we provide a number of benchmarks showing the performance characteristics of the C++ implementation, in comparison with both sequential-access and concurrent-access designs. More... »

PAGES

49-65

Book

TITLE

Model Checking Software

ISBN

978-3-319-23403-8
978-3-319-23404-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-23404-5_5

DOI

http://dx.doi.org/10.1007/978-3-319-23404-5_5

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1037367047


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Faculty of Informatics, Masaryk University, Brno, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.10267.32", 
          "name": [
            "Faculty of Informatics, Masaryk University, Brno, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Barnat", 
        "givenName": "J.", 
        "id": "sg:person.011367557177.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011367557177.46"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Informatics, Masaryk University, Brno, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.10267.32", 
          "name": [
            "Faculty of Informatics, Masaryk University, Brno, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ro\u010dkai", 
        "givenName": "P.", 
        "id": "sg:person.07377571657.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07377571657.86"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Informatics, Masaryk University, Brno, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.10267.32", 
          "name": [
            "Faculty of Informatics, Masaryk University, Brno, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "\u0160till", 
        "givenName": "V.", 
        "id": "sg:person.016057731543.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016057731543.01"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Informatics, Masaryk University, Brno, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.10267.32", 
          "name": [
            "Faculty of Informatics, Masaryk University, Brno, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Weiser", 
        "givenName": "J.", 
        "id": "sg:person.011734301511.89", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011734301511.89"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-08-27", 
    "datePublishedReg": "2015-08-27", 
    "description": "We present a new design and a C++ implementation of a high-performance, cache-efficient hash table suitable for use in implementation of parallel programs in shared memory. Among the main design criteria were the ability to efficiently use variable-length keys, dynamic table resizing to accommodate data sets of unpredictable size and fully concurrent read-write access.We show that the design is correct with respect to data races, both through a high-level argument, as well as by using a model checker to prove crucial safety properties of the actual implementation. Finally, we provide a number of benchmarks showing the performance characteristics of the C++ implementation, in comparison with both sequential-access and concurrent-access designs.", 
    "editor": [
      {
        "familyName": "Fischer", 
        "givenName": "Bernd", 
        "type": "Person"
      }, 
      {
        "familyName": "Geldenhuys", 
        "givenName": "Jaco", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-23404-5_5", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-23403-8", 
        "978-3-319-23404-5"
      ], 
      "name": "Model Checking Software", 
      "type": "Book"
    }, 
    "keywords": [
      "hash table", 
      "concurrent hash tables", 
      "crucial safety properties", 
      "variable-length keys", 
      "read-write access", 
      "high-level argument", 
      "number of benchmarks", 
      "model checker", 
      "parallel programs", 
      "data races", 
      "safety properties", 
      "unpredictable size", 
      "dynamic tables", 
      "actual implementation", 
      "data sets", 
      "main design criteria", 
      "implementation", 
      "checker", 
      "table", 
      "design", 
      "benchmarks", 
      "new design", 
      "key", 
      "design criteria", 
      "set", 
      "access", 
      "performance characteristics", 
      "memory", 
      "number", 
      "program", 
      "use", 
      "ability", 
      "respect", 
      "criteria", 
      "characteristics", 
      "comparison", 
      "size", 
      "argument", 
      "properties", 
      "race"
    ], 
    "name": "Fast, Dynamically-Sized Concurrent Hash Table", 
    "pagination": "49-65", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1037367047"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-23404-5_5"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-23404-5_5", 
      "https://app.dimensions.ai/details/publication/pub.1037367047"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:19", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_341.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-23404-5_5"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-23404-5_5'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-23404-5_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-23404-5_5'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-23404-5_5'


 

This table displays all metadata directly associated to this object as RDF triples.

125 TRIPLES      22 PREDICATES      64 URIs      57 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-23404-5_5 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N683743cbd578401d8f8c2b9f9b3dddeb
4 schema:datePublished 2015-08-27
5 schema:datePublishedReg 2015-08-27
6 schema:description We present a new design and a C++ implementation of a high-performance, cache-efficient hash table suitable for use in implementation of parallel programs in shared memory. Among the main design criteria were the ability to efficiently use variable-length keys, dynamic table resizing to accommodate data sets of unpredictable size and fully concurrent read-write access.We show that the design is correct with respect to data races, both through a high-level argument, as well as by using a model checker to prove crucial safety properties of the actual implementation. Finally, we provide a number of benchmarks showing the performance characteristics of the C++ implementation, in comparison with both sequential-access and concurrent-access designs.
7 schema:editor N4870b82ba9a0471cbdc30497b46cf210
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nbb9c58cf04c545e2abc6d25997e5b3fc
11 schema:keywords ability
12 access
13 actual implementation
14 argument
15 benchmarks
16 characteristics
17 checker
18 comparison
19 concurrent hash tables
20 criteria
21 crucial safety properties
22 data races
23 data sets
24 design
25 design criteria
26 dynamic tables
27 hash table
28 high-level argument
29 implementation
30 key
31 main design criteria
32 memory
33 model checker
34 new design
35 number
36 number of benchmarks
37 parallel programs
38 performance characteristics
39 program
40 properties
41 race
42 read-write access
43 respect
44 safety properties
45 set
46 size
47 table
48 unpredictable size
49 use
50 variable-length keys
51 schema:name Fast, Dynamically-Sized Concurrent Hash Table
52 schema:pagination 49-65
53 schema:productId N9c5dee6996234e07b10244ca1d7d2a03
54 Nf2b92eb6de014c109f3e9fb47d67d65c
55 schema:publisher Nd9b255ffc5b24649bdbda2c36167966a
56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037367047
57 https://doi.org/10.1007/978-3-319-23404-5_5
58 schema:sdDatePublished 2022-08-04T17:19
59 schema:sdLicense https://scigraph.springernature.com/explorer/license/
60 schema:sdPublisher Nc2a5c146c21549238e1ea1b18b500fd7
61 schema:url https://doi.org/10.1007/978-3-319-23404-5_5
62 sgo:license sg:explorer/license/
63 sgo:sdDataset chapters
64 rdf:type schema:Chapter
65 N17325eb340104dd2b7530b116fe1af47 schema:familyName Fischer
66 schema:givenName Bernd
67 rdf:type schema:Person
68 N2b947a1b453545fa86974889e40b16ec rdf:first sg:person.011734301511.89
69 rdf:rest rdf:nil
70 N4870b82ba9a0471cbdc30497b46cf210 rdf:first N17325eb340104dd2b7530b116fe1af47
71 rdf:rest N6b9f58ca32ca4df7a7c3e0f095691014
72 N4de5c60eb04147ec9ca498b6cbb01c76 schema:familyName Geldenhuys
73 schema:givenName Jaco
74 rdf:type schema:Person
75 N505d230256874626ab78aab74e2439f6 rdf:first sg:person.016057731543.01
76 rdf:rest N2b947a1b453545fa86974889e40b16ec
77 N683743cbd578401d8f8c2b9f9b3dddeb rdf:first sg:person.011367557177.46
78 rdf:rest Nc75f16ce80634346b80104b93cd924f1
79 N6b9f58ca32ca4df7a7c3e0f095691014 rdf:first N4de5c60eb04147ec9ca498b6cbb01c76
80 rdf:rest rdf:nil
81 N9c5dee6996234e07b10244ca1d7d2a03 schema:name doi
82 schema:value 10.1007/978-3-319-23404-5_5
83 rdf:type schema:PropertyValue
84 Nbb9c58cf04c545e2abc6d25997e5b3fc schema:isbn 978-3-319-23403-8
85 978-3-319-23404-5
86 schema:name Model Checking Software
87 rdf:type schema:Book
88 Nc2a5c146c21549238e1ea1b18b500fd7 schema:name Springer Nature - SN SciGraph project
89 rdf:type schema:Organization
90 Nc75f16ce80634346b80104b93cd924f1 rdf:first sg:person.07377571657.86
91 rdf:rest N505d230256874626ab78aab74e2439f6
92 Nd9b255ffc5b24649bdbda2c36167966a schema:name Springer Nature
93 rdf:type schema:Organisation
94 Nf2b92eb6de014c109f3e9fb47d67d65c schema:name dimensions_id
95 schema:value pub.1037367047
96 rdf:type schema:PropertyValue
97 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
98 schema:name Information and Computing Sciences
99 rdf:type schema:DefinedTerm
100 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
101 schema:name Information Systems
102 rdf:type schema:DefinedTerm
103 sg:person.011367557177.46 schema:affiliation grid-institutes:grid.10267.32
104 schema:familyName Barnat
105 schema:givenName J.
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011367557177.46
107 rdf:type schema:Person
108 sg:person.011734301511.89 schema:affiliation grid-institutes:grid.10267.32
109 schema:familyName Weiser
110 schema:givenName J.
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011734301511.89
112 rdf:type schema:Person
113 sg:person.016057731543.01 schema:affiliation grid-institutes:grid.10267.32
114 schema:familyName Štill
115 schema:givenName V.
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016057731543.01
117 rdf:type schema:Person
118 sg:person.07377571657.86 schema:affiliation grid-institutes:grid.10267.32
119 schema:familyName Ročkai
120 schema:givenName P.
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07377571657.86
122 rdf:type schema:Person
123 grid-institutes:grid.10267.32 schema:alternateName Faculty of Informatics, Masaryk University, Brno, Czech Republic
124 schema:name Faculty of Informatics, Masaryk University, Brno, Czech Republic
125 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...