Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #150166
| Path | csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail |
|---|---|
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
| Newsgroups | comp.lang.c |
| Subject | Re: Reinventing the wheel. |
| Date | Sat, 22 Feb 2020 17:06:29 -0800 |
| Organization | A noiseless patient Spider |
| Lines | 360 |
| Message-ID | <86o8tqaz8q.fsf@linuxsc.com> (permalink) |
| References | <7ca1c103-6910-48ad-8eee-b2f47e7b1db0@googlegroups.com> <r2mlau$tca$1@dont-email.me> <28633edd-9015-404a-949d-5a324c9267d9@googlegroups.com> |
| Mime-Version | 1.0 |
| Content-Type | text/plain; charset=us-ascii |
| Injection-Info | reader02.eternal-september.org; posting-host="5b1dd2a70f059f247db25722f2582bc8"; logging-data="24406"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+8FRhtNGtvfgl9qbSW6Kte4jXY1Va/n38=" |
| User-Agent | Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) |
| Cancel-Lock | sha1:vV9lc2Sl1dGtc7DnAFhGT4lf9fw= sha1:gVvis0TmGa0h/d65RdjkKMl+xuE= |
| Xref | csiph.com comp.lang.c:150166 |
Show key headers only | View raw
James Kuyper <jameskuyper@alumni.caltech.edu> writes:
> [garbled white space adjusted.. isn't google groups wonderful?]
>
> The key is a 32-bit integer, the value is 3 64-bit doubles, and
> the location is represented by a 32-bit unsigned integer.
>
> There's existing C++ code that does something similar to what my C
> code needs to do, though by a different algorithm. Both algorithms
> need to deal with different versions of the same problem that I'm
> asking about. The existing C++ code for dealing with this problem
> is functionally equivalent to the following simplified version:
>
> std::vector<Value> storage;
> std::map<std::pair<Key, Index> > newMap;
>
> // Inside the processing loop:
> auto it = newMap.find(key);
> if(it != newMap.end()) {
> value = storage[it->second];
> newMap.erase(it);
> } else {
> index = storage.size();
> value = calculate_value(key);
> storage.push_back(value);
> newMap.push_back(std::make_pair(key, index));
> }
>
> Later on, the values stored in storage get written to a file,
> along with various other data that includes indices referring to
> elements of that array.
If I understand what you're saying, what you are wanting to do (and
are still looking for) could be C code something like this, assuming
of course suitable definitions for the missing functions and types:
typedef struct { double d[3]; } Value;
static Value
calculate_value( JKHashKey key ){
return .. suitably constructed value ..;
}
void
process_key_stream_example( Value *out, unsigned maximum_active_entries ){
JKHashTable it = create_JKHashTable( maximum_active_entries );
JKHashKey key;
JKHashValue next = 0;
while( key = next_key() ){
JKHashValue *where = lookup_or_add_key_JKH( it, key );
// lookup returns a pointer to where the index value can be stored
if( ! where ){
// oops, there was an error - handle appropriately
continue;
}
if( *where == -1 ){
// New entries are given a default index value of -1
out[ next ] = calculate_value( key );
*where = next++;
} else {
// Stored value is at index previously saved in the hash table
Value v = out[ *where ];
remove_key_JKH( it, key );
}
}
release_JKHashTable( it );
}
A header file defining the interface for those functions and types
might look like this (with appropriate header file bracketing
added, naturally):
typedef struct JKHashTable_struct *JKHashTable;
typedef signed int JKHashKey;
typedef unsigned long JKHashValue;
extern JKHashTable create_JKHashTable( unsigned long maximum_active );
extern JKHashValue *lookup_or_add_key_JKH( JKHashTable, JKHashKey );
extern JKHashTable remove_key_JKH( JKHashTable, JKHashKey );
extern JKHashTable release_JKHashTable( JKHashTable );
This interface (presuming it has been saved suitably in a file
named 'jk-hash.h') can be implemented as follows. Notes given
below.
/******************************************************************
* Copyright (C) 2020 by Tim Rentsch. All rights reserved. *
* *
* Permission is granted to use this software in any way at all, *
* including derivative works, provided this copyright notice is *
* retained and subject to acknowledging and accepting my full *
* disclaimer of any and all liability. *
******************************************************************/
#include "jk-hash.h"
#include <stdlib.h>
#include <assert.h>
typedef unsigned long Index, Count, Extent, Mask, Bits;
typedef struct {
JKHashKey key;
JKHashValue value;
Index slot;
} Entry;
struct JKHashTable_struct {
Extent table_limit;
Extent entries_limit;
Index *table;
Entry *entries;
Mask slot_mask;
Count threshold;
Index entries_next;
Count occupied;
};
static JKHashTable initialize( JKHashTable, Extent, Extent );
static JKHashValue *lookup_or_add( JKHashTable it, JKHashKey key );
static JKHashTable remove_key( JKHashTable it, JKHashKey key );
static JKHashTable release( JKHashTable it );
static JKHashTable rebuild_table( JKHashTable );
static JKHashTable (checkit)( JKHashTable );
static Index slot_for( JKHashTable, JKHashKey );
static Bits rehash_for( Bits );
static Extent next_nonzero_power_of_two_at_least( Extent );
static int is_power_of_two( Bits );
JKHashTable
create_JKHashTable( unsigned long most ){
JKHashTable it = most < -2 ? calloc( 1, sizeof *it ) : 0;
Extent m = most + 2;
Extent n = m + m + m/2;
return it ? initialize( it, m, n ) : 0;
}
JKHashValue *
lookup_or_add_key_JKH( JKHashTable it, JKHashKey key ){
return it ? lookup_or_add( it, key ) : 0;
}
JKHashTable
remove_key_JKH( JKHashTable it, JKHashKey key ){
return it ? remove_key( it, key ) : 0;
}
JKHashTable
release_JKHashTable( JKHashTable it ){
return it ? release( it ) : 0;
}
/*****************************************************************************/
/*** Internal functions ***/
JKHashTable
initialize( JKHashTable it, Extent entries_needed, Extent slots_needed ){
it->table_limit = next_nonzero_power_of_two_at_least( slots_needed );
it->entries_limit = entries_needed;
it->table = calloc( it->table_limit, sizeof *it->table );
it->entries = calloc( it->entries_limit, sizeof *it->entries );
it->slot_mask = it->table_limit-1;
it->threshold = it->entries_limit +
(it->table_limit - it->entries_limit) / 2;
it->entries_next = 0;
it->occupied = 0;
if( ! is_power_of_two( it->table_limit ) ) return release( it );
if( it->table_limit <= it->entries_limit ) return release( it );
if( ! it->table ) return release( it );
if( ! it->entries ) return release( it );
it->entries[ it->entries_next++ ].slot = -1;
it->entries[ it->entries_next++ ].slot = -1;
return (checkit)( it );
}
JKHashValue *
lookup_or_add( JKHashTable it, JKHashKey key ){
Index slot = slot_for( it, key );
Entry *p = it->entries + it->table[ slot ];
if( p->slot == slot ) return (void) checkit( it ), &p->value;
if( it->entries_next == it->entries_limit ) return 0;
if( it->table[slot] == 0 ) it->occupied++;
p = &it->entries[ it->table[slot] = it->entries_next++ ];
*p = (Entry){ .key = key, .value = -1, .slot = slot };
if( it->occupied > it->threshold ) rebuild_table( it );
return (void) checkit( it ), &p->value;
}
JKHashTable
rebuild_table( JKHashTable it ){
for( Index s = 0; s < it->table_limit; s++ ) it->table[s] = 0;
it->occupied = 0;
for( Index i = 2; i < it->entries_next; i++ ){
Index slot = slot_for( it, it->entries[i].key );
assert( it->table[ slot ] == 0 );
it->table[slot] = i;
it->entries[i].slot = slot;
it->occupied ++;
}
return checkit( it );
}
JKHashTable
remove_key( JKHashTable it, JKHashKey key ){
Index slot = slot_for( it, key );
Entry *p = it->entries + it->table[slot];
if( it->table[slot] > 1 ){
*p = it->entries[ --it->entries_next ];
it->table[ p->slot ] = p - it->entries;
it->table[ slot ] = 1;
}
return checkit( it );
}
JKHashTable
release( JKHashTable it ){
free( it->table );
free( it->entries );
free( it );
return 0;
}
JKHashTable
(checkit)( JKHashTable it ){
Count occupied = 0;
for( Index slot = 0; slot < it->table_limit; slot++ ){
if( it->table[slot] ) occupied++;
}
assert( occupied == it->occupied );
for( Index i = 0; i < it->entries_next; i++ ){
Entry e = it->entries[i];
assert( i < 2 || e.slot < it->table_limit );
assert( i < 2 ? e.slot == -1 : it->table[ e.slot ] == i );
assert( i < 2 || slot_for( it, e.key ) == e.slot );
}
for( Index slot = 0; slot < it->table_limit; slot++ ){
Index k = it->table[ slot ];
assert( k < it->entries_next );
assert( k < 2 || it->entries[k].slot == slot );
}
return it;
}
Index
slot_for( JKHashTable it, JKHashKey key ){
Index fill_slot = -1, slot = key, rehash = rehash_for( slot );
Index j;
do {
j = it->table[ slot = slot+rehash & it->slot_mask ];
if( j > 1 && it->entries[j].key == key ) return slot;
if( fill_slot == -1 && j < 2 ) fill_slot = slot;
} while( j );
return assert( fill_slot < it->table_limit ), fill_slot;
}
Bits
rehash_for( Bits hash ){
static unsigned char skips[64] = {
11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97,101,103,107,109,113,127,131,137,139,147,157,
159,161,163,167,169,171,173,177,179,181,183,187,191,193,197,199,
201,203,211,213,217,219,223,227,229,231,233,237,239,241,249,251,
};
return hash < 64 ? skips[hash] : rehash_for( hash/64 + hash%64 );
}
Extent
next_nonzero_power_of_two_at_least( Extent k ){
Extent r = 1;
while( r != -1 && r+1 < k ) r += r+1;
return r+1 ? r+1 : 1;
}
int
is_power_of_two( Bits b ){
return (b & b-1) == 0;
}
/*******************************************************************
* End of C source file jk-hash.c *
*******************************************************************/
Notes:
The technique used is ordinary open addressing hashing, with double
hashing for the reprobes. To deal with deletions, removed entries
are marked with a "tombstone" value that signifies an occupied, but
not being actively used, slot. When there gets to be too many of
these -- more precisely, when occupancies exceed a pre-determined
threshold -- the table is rebuilt from the set of active entries,
so all "tombstone" slots disappear.
The only external dependencies are the standard library functions
calloc() and free(), and the assert() macro from assert.h.
There are a few assert()s in the primary code, which is to say outside
of the checkit() function. The main reason these assertions are there
is to point something out to a reader, not to catch problems.
The function checkit() is for testing and also to show invariants
that hold while a hash table is active. This function is called on
basically every action, and sometimes more than once for a given
top-level call, so it is expensive. To turn it off (except for one
call just after initialization is done), give a '-Dcheckit(a)=(a)'
option on the compilation step.
In the function 'slot_for()', the initial hash value is simply taken
directly from the key. If the keys aren't random enough, this is
the place to put in a suitable hashing function that mashes bits
of the key together so as to produce a good initial hash value.
I ran trials of various sizes, both in terms of maximum number of
active entries and how many keys total were processed. In a trial
run (with checkit() disabled) with a maximum of 65536 entries active
at any one time, a stream of one billion keys (so a billion adds
and a billion removes, maintaining 65536 entries in the hash table
all the while) took about 60 seconds.
I expect this functionality isn't exactly what you want, but it
should be close enough so the code can be adapted fairly easily to
provide the functionality you need.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-20 10:33 -0800
Re: Reinventing the wheel. Bonita Montero <Bonita.Montero@gmail.com> - 2020-02-20 20:04 +0100
Re: Reinventing the wheel. Bart <bc@freeuk.com> - 2020-02-20 19:11 +0000
Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-20 21:50 +0100
Re: Reinventing the wheel. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-20 21:01 +0000
Re: Reinventing the wheel. Bart <bc@freeuk.com> - 2020-02-20 21:34 +0000
Re: Reinventing the wheel. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-20 22:56 +0000
Re: Reinventing the wheel. Bart <bc@freeuk.com> - 2020-02-21 00:34 +0000
Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-21 09:40 +0100
Re: Reinventing the wheel. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-02-22 14:06 -0800
Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-20 20:06 +0100
Re: Reinventing the wheel. Bonita Montero <Bonita.Montero@gmail.com> - 2020-02-20 20:08 +0100
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-20 12:46 -0800
Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-20 13:55 -0800
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-21 00:12 -0500
Re: Reinventing the wheel. scott@slp53.sl.home (Scott Lurndal) - 2020-02-21 16:16 +0000
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-21 09:20 -0800
Re: Reinventing the wheel. jadill33@gmail.com - 2020-02-21 10:07 -0800
Re: Reinventing the wheel. scott@slp53.sl.home (Scott Lurndal) - 2020-02-21 23:23 +0000
Re: Reinventing the wheel. Richard Damon <Richard@Damon-Family.org> - 2020-02-21 18:41 -0500
Re: Reinventing the wheel. scott@slp53.sl.home (Scott Lurndal) - 2020-02-22 16:20 +0000
Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-22 10:33 -0800
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-22 15:00 -0500
Re: Reinventing the wheel. Richard Damon <Richard@Damon-Family.org> - 2020-02-22 15:16 -0500
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-21 08:42 -0800
Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-21 18:23 +0100
Re: Reinventing the wheel. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-02-22 17:06 -0800
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-23 06:18 -0800
Re: Reinventing the wheel. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-20 21:14 +0000
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-21 00:24 -0500
Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-20 13:15 -0800
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-20 13:44 -0800
Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-20 14:21 -0800
Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-20 14:22 -0800
Re: Reinventing the wheel. Robert Wessel <robertwessel2@yahoo.com> - 2020-02-20 15:19 -0600
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-21 00:28 -0500
Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-20 23:27 -0800
Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-20 23:52 -0800
Re: Reinventing the wheel. jadill33@gmail.com - 2020-02-21 08:20 -0800
Re: Reinventing the wheel. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-02-22 03:15 -0800
Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-22 10:38 -0800
Re: Reinventing the wheel. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-02-24 02:50 -0800
Re: Reinventing the wheel. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-02-24 16:36 +0000
Re: Reinventing the wheel. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-02-25 04:08 -0800
Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-25 13:42 +0100
Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-25 05:00 -0800
Re: Reinventing the wheel. David Brown <david.brown@hesbynett.no> - 2020-02-26 10:53 +0100
Re: Reinventing the wheel. chad <cdalten@gmail.com> - 2020-02-26 06:51 -0800
Re: Reinventing the wheel. Anton Shepelev <anton.txt@gmail.com> - 2020-02-24 22:40 +0300
Re: Reinventing the wheel. Robert Wessel <robertwessel2@yahoo.com> - 2020-02-24 16:37 -0600
Re: Reinventing the wheel. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-02-25 01:37 -0800
Re: Reinventing the wheel. Anton Shepelev <anton.txt@g{oogle}mail.com> - 2020-02-25 13:07 +0300
Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-25 04:50 -0800
Re: Reinventing the wheel. Anton Shepelev <anton.txt@g{oogle}mail.com> - 2020-02-25 19:30 +0300
Re: Reinventing the wheel. already5chosen@yahoo.com - 2020-02-25 08:43 -0800
Re: Reinventing the wheel. Anton Shepelev <anton.txt@gmail.com> - 2020-02-29 01:25 +0300
Re: Reinventing the wheel. Robert Wessel <robertwessel2@yahoo.com> - 2020-02-25 15:40 -0600
Re: Reinventing the wheel. Anton Shepelev <anton.txt@g{oogle}mail.com> - 2020-02-26 13:40 +0300
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-25 11:29 -0800
Re: Reinventing the wheel. Anton Shepelev <anton.txt@g{oogle}mail.com> - 2020-02-26 13:47 +0300
Re: Reinventing the wheel. James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-02-26 09:32 -0500
Re: Reinventing the wheel. Anton Shepelev <anton.txt@g{oogle}mail.com> - 2020-02-26 21:26 +0300
Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-02-22 23:32 -0800
Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-03-07 22:22 -0800
Re: Reinventing the wheel. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-03-07 22:38 -0800
csiph-web