Single-header C11 port of abseil.io's Swiss Table

Overview

cwisstable.h

cwisstable is a single-header C11 port of the Abseil project's Swiss Tables. This project is intended to bring the proven performance and flexibility of Swiss Tables to C projects which cannot require a C++ compiler or for projects which otherwise struggle with dependency management.

The public API is currently in flux, as is test coverage, but example.c shows off how the library can be used to create a new hash set type and insert values into it.


This is not an officially supported Google product.

Comments
  • Tests are failing on aarch64

    Tests are failing on aarch64

    Tests are failing on my raspberry pi 4.

    [email protected] ~/repos/cwisstable (main) $ lscpu
    Architecture:                    aarch64
    CPU op-mode(s):                  32-bit, 64-bit
    Byte Order:                      Little Endian
    CPU(s):                          4
    On-line CPU(s) list:             0-3
    Thread(s) per core:              1
    Core(s) per socket:              4
    Socket(s):                       1
    Vendor ID:                       ARM
    Model:                           3
    Model name:                      Cortex-A72
    Stepping:                        r0p3
    CPU max MHz:                     1500.0000
    CPU min MHz:                     600.0000
    BogoMIPS:                        108.00
    Vulnerability Itlb multihit:     Not affected
    Vulnerability L1tf:              Not affected
    Vulnerability Mds:               Not affected
    Vulnerability Meltdown:          Not affected
    Vulnerability Spec store bypass: Vulnerable
    Vulnerability Spectre v1:        Mitigation; __user pointer sanitization
    Vulnerability Spectre v2:        Vulnerable
    Vulnerability Srbds:             Not affected
    Vulnerability Tsx async abort:   Not affected
    Flags:                           fp asimd evtstrm crc32 cpuid
    
    
    [email protected] ~/repos/cwisstable (main) $ bazel version
    # bazel built from source at tag 4.2.2
    WARNING: Ignoring JAVA_HOME, because it must point to a JDK, not a JRE.
    Build label: 
    Build target: bazel-out/aarch64-opt/bin/src/main/java/com/google/devtools/build/lib/bazel/BazelServer_deploy.jar
    Build time: Sat Jan 1 01:58:05 2022 (1641002285)
    Build timestamp: 1641002285
    Build timestamp as int: 1641002285
    
    
    [email protected] ~/repos/cwisstable (main) $ bazel test ...
    WARNING: Ignoring JAVA_HOME, because it must point to a JDK, not a JRE.
    INFO: Analyzed 5 targets (0 packages loaded, 0 targets configured).
    INFO: Found 4 targets and 1 test target...
    FAIL: //test:raw_hash_set_test (see /home/widders/.cache/bazel/_bazel_widders/6f71af31bac93520e423359343e718cb/execroot/__main__/bazel-out/aarch64-fastbuild/testlogs/test/raw_hash_set_test/test.log)
    INFO: Elapsed time: 1.654s, Critical Path: 1.11s
    INFO: 2 processes: 2 linux-sandbox.
    INFO: Build completed, 1 test FAILED, 2 total actions
    //test:raw_hash_set_test                                                 FAILED in 1.0s
      /home/widders/.cache/bazel/_bazel_widders/6f71af31bac93520e423359343e718cb/execroot/__main__/bazel-out/aarch64-fastbuild/testlogs/test/raw_hash_set_test/test.log
    
    INFO: Build completed, 1 test FAILED, 2 total actions
    
    
    [email protected] ~/repos/cwisstable (main) $ cat /home/widders/.cache/bazel/_bazel_widders/6f71af31bac93520e423359343e718cb/execroot/__main__/bazel-out/aarch64-fastbuild/testlogs/test/raw_hash_set_test/test.log    
    exec ${PAGER:-/usr/bin/less} "$0" || exit 1
    Executing tests from //test:raw_hash_set_test                                              
    -----------------------------------------------------------------------------              
    Running main() from gmock_main.cc                                                          
    [==========] Running 37 tests from 5 test suites.                                          
    [----------] Global test environment set-up.
    [----------] 3 tests from Util               
    [ RUN      ] Util.NormalizeCapacity        
    [       OK ] Util.NormalizeCapacity (0 ms) 
    [ RUN      ] Util.GrowthAndCapacity        
    [       OK ] Util.GrowthAndCapacity (68 ms)
    [ RUN      ] Util.probe_seq                
    test/absl_raw_hash_set_test.cc:118: Failure                                                
    Value of: offsets                                                                          
    Expected: has 8 elements where                                                             
    element #0 is equal to 0,                                                                  
    element #1 is equal to 16,                 
    element #2 is equal to 48,                                                                 
    element #3 is equal to 96,                 
    element #4 is equal to 32,                                                                 
    element #5 is equal to 112,                                                                
    element #6 is equal to 80,                                                                 
    element #7 is equal to 64                                                                  
      Actual: { 0, 8, 24, 48, 80, 120, 40, 96 }, whose element #1 doesn't match
    test/absl_raw_hash_set_test.cc:121: Failure
    Value of: offsets                                                                                                                                                                     
    Expected: has 8 elements where                                                             
    element #0 is equal to 0,                  
    element #1 is equal to 16,        
    element #2 is equal to 48,                                                                                                                                                            
    element #3 is equal to 96,                                                                                                                                                            
    element #4 is equal to 32,                                                                                                                                                            
    element #5 is equal to 112,                                                                                                                                                           
    element #6 is equal to 80,                                                                                                                                                            
    element #7 is equal to 64                                                                                                                                                             
      Actual: { 0, 8, 24, 48, 80, 120, 40, 96 }, whose element #1 doesn't match                                                                                                           
    [  FAILED  ] Util.probe_seq (0 ms)                                                         
    [----------] 3 tests from Util (69 ms total)
                                                 
    [----------] 3 tests from BitMask                                                          
    [ RUN      ] BitMask.Smoke                                                                 
    [       OK ] BitMask.Smoke (0 ms)                                                          
    [ RUN      ] BitMask.WithShift            
    [       OK ] BitMask.WithShift (0 ms)                                                                                                                                                 
    [ RUN      ] BitMask.LeadingTrailing
    [       OK ] BitMask.LeadingTrailing (0 ms)                                                
    [----------] 3 tests from BitMask (0 ms total)                                             
                                                                                               
    [----------] 5 tests from Group                                                            
    [ RUN      ] Group.EmptyGroup                                                                                                                                                         
    [       OK ] Group.EmptyGroup (0 ms)         
    [ RUN      ] Group.Match                                                                   
    [       OK ] Group.Match (0 ms)                                                                                                                                                       
    [ RUN      ] Group.MatchEmpty
    [       OK ] Group.MatchEmpty (0 ms)       
    [ RUN      ] Group.MatchEmptyOrDeleted                                                     
    [       OK ] Group.MatchEmptyOrDeleted (0 ms)                                              
    [ RUN      ] Group.CountLeadingEmptyOrDeleted                                              
    [       OK ] Group.CountLeadingEmptyOrDeleted (0 ms)                                       
    [----------] 5 tests from Group (0 ms total)
                                                 
    [----------] 1 test from Batch             
    [ RUN      ] Batch.DropDeletes             
    test/absl_raw_hash_set_test.cc:256: Failure
    Expected equality of these values:         
      ctrl[i]                                  
        Which is: '\x2' (2)                                                                    
      expected                                                                                 
        Which is: '\xFE' (-2)                                                                  
    1 2                                                                                        
    test/absl_raw_hash_set_test.cc:256: Failure
    Expected equality of these values:                                                         
      ctrl[i]                                  
        Which is: '\xFE' (-2)                                                                  
      expected                                                                                 
        Which is: '\x80' (-128)                                                                
    2 -2                                                                                       
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:         
      ctrl[i]                                                                                                                                                                             
        Which is: '\x2' (2)                                                                    
      expected                                 
        Which is: '\xFE' (-2)         
    3 2                                                                                                                                                                                   
    test/absl_raw_hash_set_test.cc:256: Failure                                                                                                                                           
    Expected equality of these values:                                                                                                                                                    
      ctrl[i]                                                                                                                                                                             
        Which is: '\x1' (1)                                                                                                                                                               
      expected                                                                                                                                                                            
        Which is: '\xFE' (-2)                                                                                                                                                             
    5 1                                                                                        
    test/absl_raw_hash_set_test.cc:256: Failure 
    Expected equality of these values:           
      ctrl[i]                                                                                  
        Which is: '\xFE' (-2)                                                                  
      expected                                                                                 
        Which is: '\x80' (-128)               
    6 -2                                                                                                                                                                                  
    test/absl_raw_hash_set_test.cc:256: Failure
    Expected equality of these values:                                                         
      ctrl[i]                                                                                  
        Which is: '\xFE' (-2)                                                                  
      expected                                                                                 
        Which is: '\x80' (-128)                                                                                                                                                           
    9 -2                                         
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:                                                                                                                                                    
      ctrl[i]                    
        Which is: '\x2' (2)                    
      expected                                                                                 
        Which is: '\xFE' (-2)                                                                  
    10 2                                                                                       
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:          
      ctrl[i]                                    
        Which is: '\x1' (1)                    
      expected                                 
        Which is: '\xFE' (-2)                  
    12 1                                       
    test/absl_raw_hash_set_test.cc:256: Failure
    Expected equality of these values:                                                         
      ctrl[i]                                                                                  
        Which is: '\xFE' (-2)                                                                  
      expected                                                                                 
        Which is: '\x80' (-128)                
    13 -2                                                                                      
    test/absl_raw_hash_set_test.cc:256: Failure
    Expected equality of these values:                                                         
      ctrl[i]                                                                                  
        Which is: '\x2' (2)                                                                    
      expected                                                                                 
        Which is: '\xFE' (-2)                                                                  
    15 2                                       
    test/absl_raw_hash_set_test.cc:256: Failure                                                                                                                                           
    Expected equality of these values:                                                         
      ctrl[i]                                  
        Which is: '\x2' (2)           
      expected                                                                                                                                                                            
        Which is: '\xFE' (-2)                                                                                                                                                             
    17 2                                                                                                                                                                                  
    test/absl_raw_hash_set_test.cc:256: Failure                                                                                                                                           
    Expected equality of these values:                                                                                                                                                    
      ctrl[i]                                                                                                                                                                             
        Which is: '\x1' (1)                                                                                                                                                               
      expected                                                                                 
        Which is: '\xFE' (-2)                   
    19 1                                         
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:                                                         
      ctrl[i]                                                                                  
        Which is: '\xFE' (-2)                 
      expected                                                                                                                                                                            
        Which is: '\x80' (-128)                
    20 -2                                                                                      
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:                                                         
      ctrl[i]                                                                                  
        Which is: '\x2' (2)                                                                                                                                                               
      expected                                   
        Which is: '\xFE' (-2)                                                                  
    22 2                                                                                                                                                                                  
    test/absl_raw_hash_set_test.cc:256: Failure
    Expected equality of these values:         
      ctrl[i]                                                                                  
        Which is: '\xFE' (-2)                                                                  
      expected                                                                                 
        Which is: '\x80' (-128)                                                                
    23 -2                                       
    test/absl_raw_hash_set_test.cc:256: Failure  
    Expected equality of these values:         
      ctrl[i]                                  
        Which is: '\x1' (1)                    
      expected                                 
        Which is: '\xFE' (-2)                  
    26 1                                                                                       
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:                                                         
      ctrl[i]                                                                                  
        Which is: '\xFE' (-2)                  
      expected                                                                                 
        Which is: '\x80' (-128)                
    27 -2                                                                                      
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:                                                         
      ctrl[i]                                                                                  
        Which is: '\x2' (2)                                                                    
      expected                                 
        Which is: '\xFE' (-2)                                                                                                                                                             
    29 2                                                                                       
    test/absl_raw_hash_set_test.cc:256: Failure
    Expected equality of these values:
      ctrl[i]                                                                                                                                                                             
        Which is: '\xFE' (-2)                                                                                                                                                             
      expected                                                                                                                                                                            
        Which is: '\x80' (-128)                                                                                                                                                           
    30 -2                                                                                                                                                                                 
    test/absl_raw_hash_set_test.cc:256: Failure                                                                                                                                           
    Expected equality of these values:                                                                                                                                                    
      ctrl[i]                                                                                  
        Which is: '\x2' (2)                     
      expected                                   
        Which is: '\xFE' (-2)                                                                  
    31 2                                                                                       
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:        
      ctrl[i]                                                                                                                                                                             
        Which is: '\x1' (1)                    
      expected                                                                                 
        Which is: '\xFE' (-2)                                                                  
    33 1                                                                                       
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:                                                                                                                                                    
      ctrl[i]                                    
        Which is: '\xFE' (-2)                                                                  
      expected                                                                                                                                                                            
        Which is: '\x80' (-128)                
    34 -2                                      
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:                                                         
      ctrl[i]                                                                                  
        Which is: '\x2' (2)                                                                    
      expected                                  
        Which is: '\xFE' (-2)                    
    36 2                                       
    test/absl_raw_hash_set_test.cc:256: Failure
    Expected equality of these values:         
      ctrl[i]                                  
        Which is: '\xFE' (-2)                  
      expected                                                                                 
        Which is: '\x80' (-128)                                                                
    37 -2                                                                                      
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:         
      ctrl[i]                                                                                  
        Which is: '\x2' (2)                    
      expected                                                                                 
        Which is: '\xFE' (-2)                                                                  
    38 2                                                                                       
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:                                                         
      ctrl[i]                                  
        Which is: '\xFE' (-2)                                                                                                                                                             
      expected                                                                                 
        Which is: '\x80' (-128)                
    41 -2                             
    test/absl_raw_hash_set_test.cc:256: Failure                                                                                                                                           
    Expected equality of these values:                                                                                                                                                    
      ctrl[i]                                                                                                                                                                             
        Which is: '\x2' (2)                                                                                                                                                               
      expected                                                                                                                                                                            
        Which is: '\xFE' (-2)                                                                                                                                                             
    43 2                                                                                                                                                                                  
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:          
      ctrl[i]                                    
        Which is: '\xFE' (-2)                                                                  
      expected                                                                                 
        Which is: '\x80' (-128)                                                                
    44 -2                                     
    test/absl_raw_hash_set_test.cc:256: Failure                                                                                                                                           
    Expected equality of these values:         
      ctrl[i]                                                                                  
        Which is: '\x2' (2)                                                                    
      expected                                                                                 
        Which is: '\xFE' (-2)                                                                  
    45 2                                                                                                                                                                                  
    test/absl_raw_hash_set_test.cc:256: Failure  
    Expected equality of these values:                                                         
      ctrl[i]                                                                                                                                                                             
        Which is: '\x1' (1)                    
      expected                                 
        Which is: '\xFE' (-2)                                                                  
    47 1                                                                                       
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:                                                         
      ctrl[i]                                   
        Which is: '\x2' (2)                      
      expected                                 
        Which is: '\xFE' (-2)                  
    50 2                                       
    test/absl_raw_hash_set_test.cc:256: Failure
    Expected equality of these values:         
      ctrl[i]                                                                                  
        Which is: '\xFE' (-2)                                                                  
      expected                                                                                 
        Which is: '\x80' (-128)                                                                
    51 -2                                      
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:         
      ctrl[i]                                                                                  
        Which is: '\x2' (2)                                                                    
      expected                                                                                 
        Which is: '\xFE' (-2)                                                                  
    52 2                                                                                       
    test/absl_raw_hash_set_test.cc:256: Failure
    Expected equality of these values:                                                                                                                                                    
      ctrl[i]                                                                                  
        Which is: '\x1' (1)                    
      expected                        
        Which is: '\xFE' (-2)                                                                                                                                                             
    54 1                                                                                                                                                                                  
    test/absl_raw_hash_set_test.cc:256: Failure                                                                                                                                           
    Expected equality of these values:                                                                                                                                                    
      ctrl[i]                                                                                                                                                                             
        Which is: '\xFE' (-2)                                                                                                                                                             
      expected                                                                                                                                                                            
        Which is: '\x80' (-128)                                                                
    55 -2                                       
    test/absl_raw_hash_set_test.cc:256: Failure  
    Expected equality of these values:                                                         
      ctrl[i]                                                                                  
        Which is: '\x2' (2)                                                                    
      expected                                
        Which is: '\xFE' (-2)                                                                                                                                                             
    57 2                                       
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:                                                         
      ctrl[i]                                                                                  
        Which is: '\xFE' (-2)                                                                  
      expected                                                                                                                                                                            
        Which is: '\x80' (-128)                  
    58 -2                                                                                      
    test/absl_raw_hash_set_test.cc:256: Failure                                                                                                                                           
    Expected equality of these values:         
      ctrl[i]                                  
        Which is: '\x2' (2)                                                                    
      expected                                                                                 
        Which is: '\xFE' (-2)                                                                  
    59 2                                                                                       
    test/absl_raw_hash_set_test.cc:256: Failure 
    Expected equality of these values:           
      ctrl[i]                                  
        Which is: '\x1' (1)                    
      expected                                 
        Which is: '\xFE' (-2)                  
    61 1                                       
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:                                                         
      ctrl[i]                                                                                  
        Which is: '\xFE' (-2)                                                                  
      expected                                 
        Which is: '\x80' (-128)                                                                
    62 -2                                      
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:                                                         
      ctrl[i]                                                                                  
        Which is: '\x2' (2)                                                                    
      expected                                                                                 
        Which is: '\xFE' (-2)                  
    65 -2                                                                                                                                                                                 
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:         
      ctrl[i]                         
        Which is: '\xFE' (-2)                                                                                                                                                             
      expected                                                                                                                                                                            
        Which is: '\x80' (-128)                                                                                                                                                           
    66 2                                                                                                                                                                                  
    test/absl_raw_hash_set_test.cc:256: Failure                                                                                                                                           
    Expected equality of these values:                                                                                                                                                    
      ctrl[i]                                                                                                                                                                             
        Which is: '\x2' (2)                                                                    
      expected                                  
        Which is: '\xFE' (-2)                    
    67 -128                                                                                    
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:                                                         
      ctrl[i]                                 
        Which is: '\x1' (1)                                                                                                                                                               
      expected                                 
        Which is: '\xFE' (-2)                                                                  
    69 -2                                                                                      
    test/absl_raw_hash_set_test.cc:256: Failure                                                
    Expected equality of these values:                                                         
      ctrl[i]                                                                                                                                                                             
        Which is: '\xFE' (-2)                    
      expected                                                                                 
        Which is: '\x80' (-128)                                                                                                                                                           
    70 -128                                    
    [  FAILED  ] Batch.DropDeletes (4 ms)      
    [----------] 1 test from Batch (4 ms total)                                                                                                                                           
                                                                                               
    [----------] 25 tests from Table           
    [ RUN      ] Table.Empty          
    [       OK ] Table.Empty (0 ms)                                                                                                                                                       
    [ RUN      ] Table.LookupEmpty                                                                                                                                                        
    [       OK ] Table.LookupEmpty (0 ms)                                                                                                                                                 
    [ RUN      ] Table.Insert1                                                                                                                                                            
    [       OK ] Table.Insert1 (0 ms)                                                                                                                                                     
    [ RUN      ] Table.Insert2                                                                                                                                                            
    [       OK ] Table.Insert2 (0 ms)                                                                                                                                                     
    [ RUN      ] Table.InsertCollision                                                         
    [       OK ] Table.InsertCollision (0 ms)   
    [ RUN      ] Table.InsertCollisionAndFindAfterDelete
    [       OK ] Table.InsertCollisionAndFindAfterDelete (0 ms)                                
    [ RUN      ] Table.InsertWithinCapacity                                                    
    [       OK ] Table.InsertWithinCapacity (0 ms)                                             
    [ RUN      ] Table.ContainsEmpty          
    [       OK ] Table.ContainsEmpty (0 ms)                                                                                                                                               
    [ RUN      ] Table.Contains1               
    [       OK ] Table.Contains1 (0 ms)                                                        
    [ RUN      ] Table.Contains2                                                               
    [       OK ] Table.Contains2 (0 ms)                                                        
    [ RUN      ] Table.RehashWithNoResize                                                      
    [       OK ] Table.RehashWithNoResize (24 ms)                                                                                                                                         
    [ RUN      ] Table.InsertEraseStressTest     
    CWISS_CHECK failed at ./cwisstable.h:1310                                                  
    full table!                                                                                                                                                                           
    
    opened by mumbleskates 6
  • Allow emplacing values.

    Allow emplacing values.

    Right now the only way to insert into a set is via

    static inline MySet_Insert MySet_insert(MySet* self, Value* val);
    

    which performs a call to policy->copy_val. We should provide something similar to lazy_emplace that passes a callback:

    static inline MySet_Insert MySet_emplace(MySet* self, void (*cb)(void* ctx, void* slot), void* ctx);
    
    opened by mcy 1
  • Fix build on macOS

    Fix build on macOS

    There were two issues preventing cwisstable from building on macos 12.2.1 (aarch64):

    /bin/env does not exist, and should be /usr/bin/env. This works on most modern Linux systems because of the /usr/bin and /bin unification. Switching to /usr/bin/env as the canonical path adds portability.

    There was a missing ); in cwisstable/internal/control_byte.h:128.

    opened by achernya 0
  • Port over Abseil's hash function, bringing `cwisstable`'s performance on-par with Abseil's implementation

    Port over Abseil's hash function, bringing `cwisstable`'s performance on-par with Abseil's implementation

    Results:

    # Built with Clang 11
    Comparing ../absl/bazel-bin/absl/container/raw_hash_set_benchmark to ../cwisstable/bazel-bin/cwisstable_benchmark
    Benchmark                                             Time             CPU      Time Old      Time New       CPU Old       CPU New
    ----------------------------------------------------------------------------------------------------------------------------------
    BM_CacheInSteadyState/448                          +0.0028         +0.0028          2703          2711          2703          2711
    BM_CacheInSteadyState/493                          +0.0010         +0.0010          2710          2713          2710          2713
    BM_CacheInSteadyState/538                          -0.0025         -0.0024          2724          2717          2723          2717
    BM_CacheInSteadyState/583                          -0.0027         -0.0028          2731          2724          2731          2724
    BM_CacheInSteadyState/628                          +0.0519         +0.0519          2745          2887          2744          2887
    BM_CacheInSteadyState/672                          +0.0072         +0.0072          2770          2790          2770          2790
    BM_CacheInSteadyState/717                          +0.0040         +0.0040          2810          2822          2810          2821
    BM_CacheInSteadyState/762                          -0.0016         -0.0017          2828          2823          2828          2823
    BM_CacheInSteadyState/807                          -0.0071         -0.0070          2742          2722          2741          2722
    BM_CacheInSteadyState/852                          +0.0043         +0.0042          2709          2721          2709          2720
    BM_EndComparison/400                               +0.3364         +0.3364          1032          1380          1032          1380
    BM_CopyCtor/128                                    +0.1681         +0.1680           973          1136           973          1136
    BM_CopyCtor/512                                    +0.2176         +0.2177          3420          4164          3419          4164
    BM_CopyCtor/4096                                   +0.7465         +0.7465         29788         52026         29786         52021
    BM_RangeCtor/128                                   +0.1199         +0.1198           839           940           839           939
    BM_RangeCtor/512                                   +0.1368         +0.1368          3181          3616          3180          3616
    BM_RangeCtor/4096                                  +0.1198         +0.1197         26042         29162         26042         29160
    BM_RangeCtor/32768                                 +0.1381         +0.1381        231990        264016        231980        264012
    BM_RangeCtor/65536                                 +0.1271         +0.1271        503671        567683        503641        567668
    BM_NoOpReserveIntTable                             +0.0018         +0.0020             0             0             0             0
    BM_NoOpReserveStringTable                          +0.0038         +0.0038             0             0             0             0
    BM_ReserveIntTable/128                             -0.0016         -0.0014           209           209           211           210
    BM_ReserveIntTable/512                             -0.0225         -0.0224           204           200           206           201
    BM_ReserveIntTable/4096                            +0.0079         +0.0089           247           249           249           251
    BM_ReserveStringTable/128                          -0.1577         -0.1571           330           278           331           279
    BM_ReserveStringTable/512                          -0.2725         -0.2719           699           508           700           510
    BM_ReserveStringTable/4096                         -0.3481         -0.3480          4128          2691          4130          2692
    BM_Group_Match                                     +0.3488         +0.3489             1             1             1             1
    BM_Group_MatchEmpty                                +0.9604         +0.9604             0             0             0             0
    BM_Group_MatchEmptyOrDeleted                       +1.0173         +1.0173             0             0             0             0
    BM_Group_CountLeadingEmptyOrDeleted                -0.0343         -0.0345             1             1             1             1
    BM_Group_MatchFirstEmptyOrDeleted                  -0.0021         -0.0021             1             1             1             1
    BM_DropDeletes                                     +0.0219         +0.0219         31738         32431         31740         32434
    
    # Build with GCC 10
    Comparing ../absl/bazel-bin/absl/container/raw_hash_set_benchmark to ../cwisstable/bazel-bin/cwisstable_benchmark
    Benchmark                                             Time             CPU      Time Old      Time New       CPU Old       CPU New
    ----------------------------------------------------------------------------------------------------------------------------------
    BM_CacheInSteadyState/448                          -0.0490         -0.0490          3166          3011          3166          3011
    BM_CacheInSteadyState/493                          -0.0528         -0.0528          3180          3012          3179          3012
    BM_CacheInSteadyState/538                          -0.0553         -0.0553          3177          3002          3177          3001
    BM_CacheInSteadyState/583                          -0.0484         -0.0484          3176          3023          3176          3022
    BM_CacheInSteadyState/628                          -0.0564         -0.0564          3199          3019          3199          3019
    BM_CacheInSteadyState/672                          -0.0707         -0.0707          3274          3042          3273          3042
    BM_CacheInSteadyState/717                          -0.0664         -0.0665          3293          3074          3293          3074
    BM_CacheInSteadyState/762                          -0.0440         -0.0440          3246          3103          3246          3103
    BM_CacheInSteadyState/807                          -0.0450         -0.0449          3170          3027          3170          3027
    BM_CacheInSteadyState/852                          -0.0578         -0.0577          3197          3012          3196          3012
    BM_CopyCtor/128                                    +0.2766         +0.2765           824          1052           824          1052
    BM_CopyCtor/512                                    +0.0623         +0.0623          4026          4276          4025          4276
    BM_CopyCtor/4096                                   +0.1812         +0.1812         30176         35643         30176         35642
    BM_RangeCtor/128                                   +0.7614         +0.7613           799          1408           799          1408
    BM_RangeCtor/512                                   +0.7919         +0.7919          3069          5500          3069          5500
    BM_RangeCtor/4096                                  +0.7932         +0.7932         24682         44261         24681         44257
    BM_RangeCtor/32768                                 +0.8108         +0.8108        222593        403082        222588        403069
    BM_RangeCtor/65536                                 +0.8195         +0.8195        476436        866861        476426        866837
    BM_NoOpReserveIntTable                             +0.5187         +0.5188             0             1             0             1
    BM_NoOpReserveStringTable                          +1.0094         +1.0096             0             1             0             1
    BM_ReserveIntTable/128                             +0.1047         +0.1042           197           217           198           219
    BM_ReserveIntTable/512                             -0.0018         -0.0024           204           203           205           205
    BM_ReserveIntTable/4096                            +0.0150         +0.0143           252           256           254           257
    BM_ReserveStringTable/128                          +0.1848         +0.1827           281           333           282           334
    BM_ReserveStringTable/512                          +0.4848         +0.4835           467           694           468           695
    BM_ReserveStringTable/4096                         +0.8470         +0.8464          2236          4129          2237          4131
    BM_Group_Match                                     +0.0001         +0.0001             2             2             2             2
    BM_Group_MatchEmpty                                -0.0047         -0.0046             2             2             2             2
    BM_Group_MatchEmptyOrDeleted                       +0.0057         +0.0057             2             2             2             2
    BM_Group_CountLeadingEmptyOrDeleted                +0.0039         +0.0039             2             2             2             2
    BM_Group_MatchFirstEmptyOrDeleted                  +0.0018         +0.0018             2             2             2             2
    BM_DropDeletes                                     +0.0218         +0.0218         32139         32839         32137         32837
    

    For the key benchmark, BM_CacheInSteadyState, we perform no worse than Abseil within statistical uncertainty of +/-5%. Currently, we are measurably worse at copying, which may be due to sloppy porting of the benchmark in BM_RangeCtor.

    That said, I think we can accurately conclude that cwisstable is a viable SwissTable implementation!

    opened by mcy 0
  • Add deferred insertion

    Add deferred insertion

    You can now insert a completely different value from the one you were going to try to insert before calling insert; in other words, deferred insertion returns the place where the value would have been inserted, giving you a chance to do it your way!

    MyArrayMap_Insert in = MyArrayMap_deferred_insert_by_IntView(&map, &k);
    assert(in.inserted);
    v = MyArrayMap_Iter_get(&in.iter);
    v->key = IntArray_from_view(k);
    v->val = 42;
    
    opened by mcy 0
  • Implement heterogenous lookup and erasure

    Implement heterogenous lookup and erasure

    Adds CWISS_DECLARE_LOOKUP and CWISS_DECLARE_LOOKUP_NAMED which can be used to generate "heterogenous" lookup functions for a specific map type. For example

    static inline size_t MyArrayMap_IntView_hash(const IntView* self) {
      CWISS_FxHash_State state = 0;
      CWISS_FxHash_Write(&state, &self->len, sizeof(self->len));
      CWISS_FxHash_Write(&state, self->ptr, self->len * sizeof(int));
      return state;
    }
    
    static inline bool MyArrayMap_IntView_eq(const IntView* self,
                                             const MyArrayMap_Entry* that) {
      IntArray_dump(&that->key);
      return self->len == that->key.len &&
             memcmp(self->ptr, that->key.ptr, self->len * sizeof(int)) == 0;
    }
    
    CWISS_DECLARE_LOOKUP(MyArrayMap, IntView);
    
    // ...
    
    int buf[5] = {2, 3, 4};
    IntView k = {buf, 3};
    assert(!MyArrayMap_contains_by_IntView(&map, &k));
    

    Also refactors some of the internals to pass around two policies inside of certain key functions.

    opened by mcy 0
  • Add documentation for all public parts of the project

    Add documentation for all public parts of the project

    This change ended up being very packed, since I refactored the policy builder API (again). However, the resulting product should be well-polished at this point.

    opened by mcy 0
  • Break cwisstable.h into several files

    Break cwisstable.h into several files

    Although this project's goal is to have a single-file SwissTable, doing so in practice is a bit painful from a maintenance perspective. We strike a balance: for development, we have split files, but a script can deterministically regenerate the unified header, which is considered authoritative.

    opened by mcy 0
  • Add benchmarks, copied from Abseil

    Add benchmarks, copied from Abseil

    Here's the results using Clang 11:

    ----------------------------------------------------------------------------------------------
    Benchmark                                    Time             CPU   Iterations UserCounters...
    ----------------------------------------------------------------------------------------------
    BM_CacheInSteadyState/448                 2232 ns         2232 ns       309159 items_per_second=448.102k/s load_factor=0.59
    BM_CacheInSteadyState/493                 2224 ns         2224 ns       320068 items_per_second=449.731k/s load_factor=0.61
    BM_CacheInSteadyState/538                 2214 ns         2214 ns       322539 items_per_second=451.694k/s load_factor=0.62
    BM_CacheInSteadyState/583                 2215 ns         2215 ns       322032 items_per_second=451.522k/s load_factor=0.62
    BM_CacheInSteadyState/628                 2212 ns         2212 ns       322424 items_per_second=452.158k/s load_factor=0.62
    BM_CacheInSteadyState/672                 2218 ns         2217 ns       322225 items_per_second=450.972k/s load_factor=0.62
    BM_CacheInSteadyState/717                 2214 ns         2214 ns       322496 items_per_second=451.617k/s load_factor=0.62
    BM_CacheInSteadyState/762                 2229 ns         2229 ns       322047 items_per_second=448.711k/s load_factor=0.62
    BM_CacheInSteadyState/807                 2216 ns         2216 ns       322067 items_per_second=451.294k/s load_factor=0.62
    BM_CacheInSteadyState/852                 2228 ns         2228 ns       317848 items_per_second=448.859k/s load_factor=0.61
    BM_EndComparison/400                      3709 ns         3709 ns       180071
    BM_CopyCtor/128                            903 ns          903 ns       744500
    BM_CopyCtor/512                           3880 ns         3880 ns       179235
    BM_CopyCtor/4096                         37252 ns        37250 ns        18846
    BM_CopyAssign/128                          888 ns          888 ns       765713
    BM_CopyAssign/512                         3969 ns         3968 ns       180412
    BM_CopyAssign/4096                       37720 ns        37718 ns        19104
    BM_RangeCtor/128                          2016 ns         2016 ns       349198
    BM_RangeCtor/512                          7729 ns         7729 ns        91334
    BM_RangeCtor/4096                        63973 ns        63971 ns        11215
    BM_RangeCtor/32768                      536555 ns       536539 ns         1308
    BM_RangeCtor/65536                     1138317 ns      1138290 ns          619
    BM_NoOpReserveIntTable                   0.298 ns        0.298 ns   1000000000
    BM_NoOpReserveStringTable                0.298 ns        0.298 ns   1000000000
    BM_ReserveIntTable/128                     324 ns          324 ns      2863146
    BM_ReserveIntTable/512                     224 ns          225 ns      2465474
    BM_ReserveIntTable/4096                    270 ns          271 ns      2565834
    BM_ReserveStringTable/128                  219 ns          220 ns      3142603
    BM_ReserveStringTable/512                  224 ns          225 ns      3043189
    BM_ReserveStringTable/4096                 267 ns          268 ns      2597648
    BM_Group_Match                           0.541 ns        0.541 ns   1000000000
    BM_Group_MatchEmpty                      0.476 ns        0.476 ns   1000000000
    BM_Group_MatchEmptyOrDeleted             0.478 ns        0.478 ns   1000000000
    BM_Group_CountLeadingEmptyOrDeleted      0.952 ns        0.952 ns    734777535
    BM_Group_MatchFirstEmptyOrDeleted        0.713 ns        0.713 ns    983451904
    BM_DropDeletes                           32562 ns        32551 ns        21400
    

    Here's the same output from Abseil:

    ----------------------------------------------------------------------------------------------
    Benchmark                                    Time             CPU   Iterations UserCounters...
    ----------------------------------------------------------------------------------------------
    BM_CacheInSteadyState/448                 2781 ns         2781 ns       247619 items_per_second=359.633k/s load_factor=0.44
    BM_CacheInSteadyState/493                 2741 ns         2741 ns       255531 items_per_second=364.776k/s load_factor=0.48
    BM_CacheInSteadyState/538                 2751 ns         2751 ns       253919 items_per_second=363.508k/s load_factor=0.53
    BM_CacheInSteadyState/583                 2765 ns         2765 ns       253144 items_per_second=361.687k/s load_factor=0.57
    BM_CacheInSteadyState/628                 2773 ns         2773 ns       252960 items_per_second=360.669k/s load_factor=0.61
    BM_CacheInSteadyState/672                 2778 ns         2778 ns       250945 items_per_second=359.985k/s load_factor=0.66
    BM_CacheInSteadyState/717                 2833 ns         2833 ns       249320 items_per_second=352.995k/s load_factor=0.70
    BM_CacheInSteadyState/762                 2851 ns         2851 ns       244764 items_per_second=350.786k/s load_factor=0.74
    BM_CacheInSteadyState/807                 2735 ns         2735 ns       256760 items_per_second=365.677k/s load_factor=0.39
    BM_CacheInSteadyState/852                 2748 ns         2748 ns       256493 items_per_second=363.846k/s load_factor=0.42
    BM_EndComparison/400                      1060 ns         1060 ns       669219
    BM_CopyCtor/128                            787 ns          787 ns       881932
    BM_CopyCtor/512                           3517 ns         3517 ns       200668
    BM_CopyCtor/4096                         29573 ns        29570 ns        22948
    BM_CopyAssign/128                          972 ns          972 ns       717030
    BM_CopyAssign/512                         3646 ns         3646 ns       192541
    BM_CopyAssign/4096                       31746 ns        31744 ns        21872
    BM_RangeCtor/128                           864 ns          864 ns       805573
    BM_RangeCtor/512                          3321 ns         3321 ns       214459
    BM_RangeCtor/4096                        26328 ns        26327 ns        26564
    BM_RangeCtor/32768                      236531 ns       236504 ns         2971
    BM_RangeCtor/65536                      508034 ns       508021 ns         1375
    BM_NoOpReserveIntTable                   0.298 ns        0.298 ns   1000000000
    BM_NoOpReserveStringTable                0.299 ns        0.299 ns   1000000000
    BM_ReserveIntTable/128                     211 ns          213 ns      3305282
    BM_ReserveIntTable/512                     204 ns          205 ns      3437311
    BM_ReserveIntTable/4096                    252 ns          253 ns      2769420
    BM_ReserveStringTable/128                  335 ns          337 ns      2063183
    BM_ReserveStringTable/512                  700 ns          702 ns       994710
    BM_ReserveStringTable/4096                4149 ns         4150 ns       168774
    BM_Group_Match                           0.529 ns        0.529 ns   1000000000
    BM_Group_MatchEmpty                      0.237 ns        0.237 ns   1000000000
    BM_Group_MatchEmptyOrDeleted             0.237 ns        0.237 ns   1000000000
    BM_Group_CountLeadingEmptyOrDeleted      0.945 ns        0.945 ns    739763501
    BM_Group_MatchFirstEmptyOrDeleted        0.712 ns        0.712 ns    984603599
    BM_DropDeletes                           31881 ns        31885 ns        22013
    

    With clang, we appear to take a 2x performance hit! CacheInSteadyState is about the same because our version is a set, not a map, using only a single std::string.

    GCC 10, on the other hand, puts them on par. Note that EndComparison is miscompiled on GCC.

    Ours:

    ----------------------------------------------------------------------------------------------
    Benchmark                                    Time             CPU   Iterations UserCounters...
    ----------------------------------------------------------------------------------------------
    BM_CacheInSteadyState/448                 3654 ns         3654 ns       195743 items_per_second=273.666k/s load_factor=0.75
    BM_CacheInSteadyState/493                 3498 ns         3498 ns       199919 items_per_second=285.879k/s load_factor=0.76
    BM_CacheInSteadyState/538                 3487 ns         3487 ns       200594 items_per_second=286.764k/s load_factor=0.77
    BM_CacheInSteadyState/583                 3498 ns         3497 ns       200677 items_per_second=285.937k/s load_factor=0.77
    BM_CacheInSteadyState/628                 3500 ns         3500 ns       200473 items_per_second=285.746k/s load_factor=0.77
    BM_CacheInSteadyState/672                 3495 ns         3495 ns       200936 items_per_second=286.138k/s load_factor=0.77
    BM_CacheInSteadyState/717                 3489 ns         3489 ns       200725 items_per_second=286.612k/s load_factor=0.77
    BM_CacheInSteadyState/762                 3490 ns         3490 ns       200524 items_per_second=286.57k/s load_factor=0.77
    BM_CacheInSteadyState/807                 3497 ns         3497 ns       200474 items_per_second=285.979k/s load_factor=0.77
    BM_CacheInSteadyState/852                 3492 ns         3492 ns       199342 items_per_second=286.369k/s load_factor=0.76
    BM_EndComparison/400                      1404 ns         1403 ns       567467
    BM_CopyCtor/128                           1059 ns         1058 ns       640524
    BM_CopyCtor/512                           4294 ns         4294 ns       161440
    BM_CopyCtor/4096                         35340 ns        35336 ns        19843
    BM_CopyAssign/128                         1059 ns         1059 ns       657347
    BM_CopyAssign/512                         4365 ns         4365 ns       161204
    BM_CopyAssign/4096                       35335 ns        35333 ns        19723
    BM_RangeCtor/128                          1626 ns         1625 ns       416731
    BM_RangeCtor/512                          6641 ns         6641 ns       108411
    BM_RangeCtor/4096                        51736 ns        51734 ns        13550
    BM_RangeCtor/32768                      450926 ns       450917 ns         1557
    BM_RangeCtor/65536                      970027 ns       969893 ns          729
    BM_NoOpReserveIntTable                   0.470 ns        0.470 ns   1000000000
    BM_NoOpReserveStringTable                0.469 ns        0.469 ns   1000000000
    BM_ReserveIntTable/128                     220 ns          222 ns      3176938
    BM_ReserveIntTable/512                     209 ns          210 ns      3317878
    BM_ReserveIntTable/4096                    256 ns          258 ns      2734051
    BM_ReserveStringTable/128                  208 ns          209 ns      3372560
    BM_ReserveStringTable/512                  210 ns          211 ns      3310008
    BM_ReserveStringTable/4096                 261 ns          263 ns      2700252
    BM_Group_Match                            2.07 ns         2.03 ns    355478853
    BM_Group_MatchEmpty                       2.01 ns         2.01 ns    342197416
    BM_Group_MatchEmptyOrDeleted              1.90 ns         1.90 ns    363496692
    BM_Group_CountLeadingEmptyOrDeleted       1.93 ns         1.93 ns    354012034
    BM_Group_MatchFirstEmptyOrDeleted         1.89 ns         1.89 ns    369066830
    BM_DropDeletes                           26443 ns        26430 ns        26620
    

    Abseil's:

    ----------------------------------------------------------------------------------------------
    Benchmark                                    Time             CPU   Iterations UserCounters...
    ----------------------------------------------------------------------------------------------
    BM_CacheInSteadyState/448                 3219 ns         3219 ns       215551 items_per_second=310.643k/s load_factor=0.44
    BM_CacheInSteadyState/493                 3178 ns         3178 ns       218778 items_per_second=314.7k/s load_factor=0.48
    BM_CacheInSteadyState/538                 3184 ns         3184 ns       220123 items_per_second=314.117k/s load_factor=0.53
    BM_CacheInSteadyState/583                 3192 ns         3192 ns       219408 items_per_second=313.281k/s load_factor=0.57
    BM_CacheInSteadyState/628                 3196 ns         3196 ns       218619 items_per_second=312.874k/s load_factor=0.61
    BM_CacheInSteadyState/672                 3218 ns         3218 ns       217704 items_per_second=310.789k/s load_factor=0.66
    BM_CacheInSteadyState/717                 3239 ns         3239 ns       215716 items_per_second=308.783k/s load_factor=0.70
    BM_CacheInSteadyState/762                 3270 ns         3270 ns       214419 items_per_second=305.817k/s load_factor=0.74
    BM_CacheInSteadyState/807                 3172 ns         3172 ns       220473 items_per_second=315.24k/s load_factor=0.39
    BM_CacheInSteadyState/852                 3218 ns         3218 ns       219759 items_per_second=310.717k/s load_factor=0.42
    BM_EndComparison/400                       445 ns          445 ns      1599732
    BM_CopyCtor/128                            737 ns          737 ns       919820
    BM_CopyCtor/512                           3431 ns         3430 ns       202455
    BM_CopyCtor/4096                         25420 ns        25419 ns        27220
    BM_CopyAssign/128                          850 ns          850 ns       835429
    BM_CopyAssign/512                         3729 ns         3729 ns       188703
    BM_CopyAssign/4096                       27333 ns        27333 ns        25649
    BM_RangeCtor/128                           826 ns          826 ns       903980
    BM_RangeCtor/512                          2990 ns         2990 ns       229992
    BM_RangeCtor/4096                        25182 ns        25181 ns        28377
    BM_RangeCtor/32768                      220809 ns       220795 ns         3174
    BM_RangeCtor/65536                      477403 ns       477389 ns         1463
    BM_NoOpReserveIntTable                   0.472 ns        0.472 ns   1000000000
    BM_NoOpReserveStringTable                0.472 ns        0.472 ns   1000000000
    BM_ReserveIntTable/128                     214 ns          215 ns      3241154
    BM_ReserveIntTable/512                     206 ns          207 ns      3367336
    BM_ReserveIntTable/4096                    252 ns          254 ns      2741430
    BM_ReserveStringTable/128                  278 ns          280 ns      2507610
    BM_ReserveStringTable/512                  466 ns          467 ns      1496864
    BM_ReserveStringTable/4096                2231 ns         2232 ns       313415
    BM_Group_Match                            1.87 ns         1.87 ns    374214578
    BM_Group_MatchEmpty                       1.87 ns         1.87 ns    374817934
    BM_Group_MatchEmptyOrDeleted              1.88 ns         1.88 ns    373993675
    BM_Group_CountLeadingEmptyOrDeleted       1.88 ns         1.88 ns    370733499
    BM_Group_MatchFirstEmptyOrDeleted         1.87 ns         1.87 ns    372861128
    BM_DropDeletes                           32630 ns        32635 ns        21507
    

    I suspect the difference here is that Clang is not inlining as aggressively as it needs to, from comparing generated assembly. For example, the GCC codegen for CodegenAbslRawHashSetInt64FindNeEnd is vastly more flat.

    opened by mcy 0
  • Refactor user-facing macros to make certain constructions less painful.

    Refactor user-facing macros to make certain constructions less painful.

    example.c has an example into how you would (with great pain and suffering) assemble the moral equivalent of absl::node_hash_map<std::string, float> in C.

    Fixes https://github.com/google/cwisstable/issues/5.

    opened by mcy 0
  • Write up a style guide

    Write up a style guide

    The code right now looks like a strange amalgamation of Google C++ with C idioms. We should write down some norms and practices of where we deviate from Google C++ for consistency.

    opened by mcy 0
  • Add ahash as an alternative hash function

    Add ahash as an alternative hash function

    Even though my benchmarks for Rust show that ahash destroys absl hash, this port apparently performs up to 4x worse, so something is messed up in the codegen somewhere; I need to debug this.

    To give an idea of what the Rust benchmarks look like:

    absl/i64                time:   [3.0473 ms 3.0492 ms 3.0520 ms]
    ahash/i64               time:   [1.5593 ms 1.5654 ms 1.5720 ms]
    absl/small &[u8]        time:   [6.0225 ms 6.0371 ms 6.0561 ms]  
    ahash/small &[u8]       time:   [3.5620 ms 3.5657 ms 3.5696 ms]
    

    Meanwhile, the C++ benchmarks are terrible:

    CC=clang bazel run :cwisstable_benchmark -c opt
    ----------------------------------------------------------------------------------------------
    Benchmark                                    Time             CPU   Iterations UserCounters...
    ----------------------------------------------------------------------------------------------
    BM_CacheInSteadyState/448                14795 ns        14795 ns        42799 items_per_second=67.5905k/s load_factor=0.44
    BM_CacheInSteadyState/493                14791 ns        14790 ns        47326 items_per_second=67.6126k/s load_factor=0.48
    BM_CacheInSteadyState/538                14816 ns        14815 ns        47223 items_per_second=67.4983k/s load_factor=0.53
    BM_CacheInSteadyState/583                14810 ns        14809 ns        47305 items_per_second=67.5271k/s load_factor=0.57
    BM_CacheInSteadyState/628                14844 ns        14843 ns        47164 items_per_second=67.3697k/s load_factor=0.61
    BM_CacheInSteadyState/672                14837 ns        14837 ns        47116 items_per_second=67.3997k/s load_factor=0.66
    BM_CacheInSteadyState/717                14874 ns        14873 ns        47026 items_per_second=67.2371k/s load_factor=0.70
    BM_CacheInSteadyState/762                14929 ns        14928 ns        46896 items_per_second=66.9872k/s load_factor=0.74
    BM_CacheInSteadyState/807                14793 ns        14792 ns        47508 items_per_second=67.6026k/s load_factor=0.39
    BM_CacheInSteadyState/852                14832 ns        14832 ns        47399 items_per_second=67.4224k/s load_factor=0.42
    BM_EndComparison/400                      1391 ns         1391 ns       505350
    BM_CopyCtor/128                           1480 ns         1480 ns       467681
    BM_CopyCtor/512                           6062 ns         6062 ns       117797
    BM_CopyCtor/4096                         55412 ns        55407 ns        12656
    BM_RangeCtor/128                          7269 ns         7269 ns        96470
    BM_RangeCtor/512                         29014 ns        29012 ns        24230
    BM_RangeCtor/4096                       235547 ns       235536 ns         2964
    BM_RangeCtor/32768                     2022793 ns      2022756 ns          346
    BM_RangeCtor/65536                     4268254 ns      4268095 ns          164
    BM_NoOpReserveIntTable                   0.234 ns        0.234 ns   1000000000
    BM_NoOpReserveStringTable                0.235 ns        0.235 ns   1000000000
    BM_ReserveIntTable/128                     213 ns          214 ns      3291830
    BM_ReserveIntTable/512                     213 ns          214 ns      3250297
    BM_ReserveIntTable/4096                    264 ns          265 ns      2637759
    BM_ReserveStringTable/128                  297 ns          298 ns      2349449
    BM_ReserveStringTable/512                  529 ns          530 ns      1314091
    BM_ReserveStringTable/4096                2770 ns         2771 ns       253236
    BM_Group_Match                           0.499 ns        0.499 ns   1000000000
    BM_Group_MatchEmpty                      0.471 ns        0.471 ns   1000000000
    BM_Group_MatchEmptyOrDeleted             0.469 ns        0.469 ns   1000000000
    BM_Group_CountLeadingEmptyOrDeleted      0.468 ns        0.467 ns   1000000000
    BM_Group_MatchFirstEmptyOrDeleted        0.452 ns        0.452 ns   1000000000
    BM_DropDeletes                           32202 ns        32197 ns        22220
    
    CC=clang bazel run :cwisstable_benchmark_no_aes -c opt
    ----------------------------------------------------------------------------------------------
    Benchmark                                    Time             CPU   Iterations UserCounters...
    ----------------------------------------------------------------------------------------------
    BM_CacheInSteadyState/448                 9684 ns         9683 ns        58926 items_per_second=103.269k/s load_factor=0.44
    BM_CacheInSteadyState/493                 9693 ns         9693 ns        71853 items_per_second=103.167k/s load_factor=0.48
    BM_CacheInSteadyState/538                 9708 ns         9708 ns        72320 items_per_second=103.01k/s load_factor=0.53
    BM_CacheInSteadyState/583                 9714 ns         9713 ns        72044 items_per_second=102.953k/s load_factor=0.57
    BM_CacheInSteadyState/628                 9721 ns         9720 ns        72163 items_per_second=102.876k/s load_factor=0.61
    BM_CacheInSteadyState/672                 9750 ns         9750 ns        71999 items_per_second=102.569k/s load_factor=0.66
    BM_CacheInSteadyState/717                 9760 ns         9759 ns        71722 items_per_second=102.466k/s load_factor=0.70
    BM_CacheInSteadyState/762                 9837 ns         9837 ns        71413 items_per_second=101.66k/s load_factor=0.74
    BM_CacheInSteadyState/807                 9696 ns         9696 ns        72910 items_per_second=103.139k/s load_factor=0.39
    BM_CacheInSteadyState/852                 9699 ns         9698 ns        72519 items_per_second=103.114k/s load_factor=0.42
    BM_EndComparison/400                      1322 ns         1322 ns       511558
    BM_CopyCtor/128                           1093 ns         1093 ns       648516
    BM_CopyCtor/512                           4528 ns         4528 ns       159269
    BM_CopyCtor/4096                         45876 ns        45872 ns        15028
    BM_RangeCtor/128                           868 ns          868 ns       813842
    BM_RangeCtor/512                          3216 ns         3215 ns       218478
    BM_RangeCtor/4096                        25949 ns        25948 ns        27169
    BM_RangeCtor/32768                      242875 ns       242838 ns         2823
    BM_RangeCtor/65536                      520697 ns       520687 ns         1335
    BM_NoOpReserveIntTable                   0.234 ns        0.234 ns   1000000000
    BM_NoOpReserveStringTable                0.233 ns        0.233 ns   1000000000
    BM_ReserveIntTable/128                     206 ns          208 ns      3334134
    BM_ReserveIntTable/512                     209 ns          211 ns      3322353
    BM_ReserveIntTable/4096                    269 ns          270 ns      2628556
    BM_ReserveStringTable/128                  298 ns          299 ns      2340071
    BM_ReserveStringTable/512                  530 ns          531 ns      1323468
    BM_ReserveStringTable/4096                2766 ns         2768 ns       253804
    BM_Group_Match                           0.474 ns        0.474 ns   1000000000
    BM_Group_MatchEmpty                      0.472 ns        0.472 ns   1000000000
    BM_Group_MatchEmptyOrDeleted             0.472 ns        0.472 ns   1000000000
    BM_Group_CountLeadingEmptyOrDeleted      0.469 ns        0.469 ns   1000000000
    BM_Group_MatchFirstEmptyOrDeleted        0.456 ns        0.456 ns   1000000000
    BM_DropDeletes                           20700 ns        20704 ns        33807
    
    opened by mcy 1
  • Build fails with clang

    Build fails with clang

    The tests fail to compile when using Clang.

    In file included from examples/hashset.c:22:
    In file included from ./cwisstable/declare.h:22:
    ./cwisstable/internal/raw_table.h:326:10: error: variable 'total_probe_length' set but not used [-Werror,-Wunused-but-set-variable]
      size_t total_probe_length = 0;
             ^
    ./cwisstable/internal/raw_table.h:378:10: error: variable 'total_probe_length' set but not used [-Werror,-Wunused-but-set-variable]
      size_t total_probe_length = 0;
             ^
    
    $ cc --version
    Ubuntu clang version 15.0.0-++20220206114023+bad1b7fbb0fe-1~exp1~20220206114123.276
    Target: x86_64-pc-linux-gnu
    Thread model: posix
    InstalledDir: /usr/bin
    
    opened by mumbleskates 0
  • Add documentation comments to `cwisstable.h`

    Add documentation comments to `cwisstable.h`

    The main file, cwisstable.h, should have very detailed documentation, references to the equivalent files in Abseil, the Swiss Table design doc, other things.

    • [x] Top-of-file comment.
    • [ ] What define-based interface do we expose?
    • [ ] Which APIs are public?
    • [x] Comment explaining policies.
    • [x] Comment explaining generated APIs from CWISS_DECLARE_* macros.
    opened by mcy 0
Owner
Google
Google ❤️ Open Source
Google
CHIP-8 interpreter in C11

shoganai | しょうがない It means accepting what happens beyond our control and cannot be avoided. It is used to encourage people to move forward without bei

Gioele 2 Sep 28, 2021
Macro magic for declaring/calling Objective-C APIs from C11 or C++. Preloads selectors, chooses the correct objc_msgSend to call per method/platform.

OC - Easily Declare/Invoke Objective-C APIs from C11 or C++11 Usage // Call class and instance methods: NSWindow* const nswindow = oc_cls(NSWindow,new

Garett Bass 45 Sep 9, 2022
A Modern C11 compiler (STILL EARLY)

Cuik (pronounced 'Quick') warning: unfinished The plan is a modern C11 compiler which can mostly work with Clang, GCC, and MSVC while also introducing

Yasser Arguelles 111 Nov 23, 2022
A simple and sample port of ceserver to iOS.

A simple and sample port of ceserver to iOS.This project is currently under development.

KenjiroIchise 1 Oct 19, 2021
A single file, single function, header to make notifications on the PS4 easier

Notifi Synopsis Adds a single function notifi(). It functions like printf however the first arg is the image to use (NULL and any invalid input should

Al Azif 9 Oct 4, 2022
Table Maker for Modern C++

Source for the above image can be found here Table of Contents Quick Start Formatting Options Style Inheritance Model Word Wrapping Font Alignment Fon

Pranav 1.4k Nov 22, 2022
The simple UEFI application to create a Windows Platform Binary Table (WPBT) from the UEFI shell.

WPBT Builder This is a simple UEFI application to create a Windows Platform Binary Table (WPBT) from the UEFI shell. Motivation WPBT is one of the Adv

Satoshi Tanda 70 Nov 23, 2022
Code for our ECE445/ME470 design: Wireless Charging Table with Automatic Alignment

Qi Wireless Charging Table with Automatic Alignment Code for ECE445/ME470 Senior Design Project SP21 at ZJUI. Team 24: Kaiwen Cao, Tianyi Han, Tingkai

Zikai Liu 2 May 1, 2022
Project uses an Arduino Leonardo to interface an A1UP Street Fighter Table controller boards with a pc.

Street Fighter Arcade1Up Table Arduino Interface Goal of this project Arcade1Up uses proprietary circuit boards to interface with the game's circuit b

Christopher Perkins 1 Oct 27, 2021
Code for an air hockey table for an engineering project.

Project: Air Hockey Table Code for an air hockey table. Step 1: Installation Step 2: Assemble the circuit Assemble the circuit following the diagram l

William Rice 3 Jan 21, 2022
C++11 provides chainable and iterable object for uniform die casts. Useful for statistics or table top RPG simulations.

12/1/2018 Due to feedback about compile-time limitations, the api has been changed since release. The api now supports user-defined literals which mak

null 12 Sep 5, 2021
MFAT is a minimal I/O library for FAT (File Allocation Table) volumes.

MFAT MFAT is a minimal I/O library for FAT (File Allocation Table) volumes. The library has been designed for embedded systems, and its small code and

null 6 Nov 26, 2022
Single-header, ranges-compatible generator type built on C++20 coroutines

generator Single-header, ranges-compatible generator type built with C++20 coroutines. A generator allows implementing sequence producers which are te

Sy Brand 36 Nov 16, 2022
Collection of cross-platform single-header C libraries for doing a lot of stuff! (Still WIP)

ice_libs Collection of cross-platform single-header C libraries for doing a lot of stuff! (Still WIP) Brief ice_libs is collection of Single-Header C

Rabia Alhaffar 117 Dec 2, 2022
stackwalkerc - Windows single header stack walker in C (DbgHelp.DLL)

stackwalkerc - Windows single header stack walker in C (DbgHelp.DLL) Features Can be used in C or C++ code Super simple API Single header library make

Sepehr Taghdisian 29 Jul 4, 2022
A single-header C/C++ library for parsing and evaluation of arithmetic expressions

ceval A C/C++ header for parsing and evaluation of arithmetic expressions. [README file is almost identical to that of the ceval library] Functions ac

e_t 9 Oct 10, 2022
A single-header C/C++ library for parsing and evaluation of arithmetic expressions

ceval A C/C++ header for parsing and evaluation of arithmetic expressions. [README file is almost identical to that of the ceval library] Functions ac

e_t 9 Oct 10, 2022
A single-header, new syntax for C & C++

sea A new syntax for C & C++, in one header file sea is a new syntax for C & C++. It can be used by adding the following line of code to a .c, or .cc/

Cloud Worm 1 Nov 19, 2021
base64 single header encode/decode

b64.h base64 single header encode/decode #include <stdio.h> #include "b64.h" // strings are stored on the heap, don't forget to free() them int main(i

null 4 Jul 27, 2022