Groups > comp.lang.c > #150093 > unrolled thread

Reinventing the wheel.

Started by	James Kuyper <jameskuyper@alumni.caltech.edu>
First post	2020-02-20 10:33 -0800
Last post	2020-03-07 22:38 -0800
Articles	20 on this page of 65 — 16 participants

Back to article view | Back to comp.lang.c

  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

Page 2 of 4 — ← Prev page 1 [2] 3 4 Next page →

#150149

From	scott@slp53.sl.home (Scott Lurndal)
Date	2020-02-22 16:20 +0000
Message-ID	<Ixc4G.546023$Gh7.44911@fx45.iad>
In reply to	#150133

Richard Damon <Richard@Damon-Family.org> writes:
>On 2/21/20 6:23 PM, Scott Lurndal wrote:
>> James Kuyper <jameskuyper@alumni.caltech.edu> writes:
>>> Scott Lurndal wrote:
>>>> In the several days this discussion has been in process,
>> 
>>>
>>> Not particularly. So long as it's not significantly slower
>>> than the algorithm it will be replacing (which uses C++ and
>>> std::map<>), I should be fine - I just want to be sure that
>>> it will be no slower. I'm primarily interested in ease of
>>> implementation. The Subject of this thread was chosen to
>>> express my annoyance at having to reimplement something
>>> that has been implemented and thoroughly tested many times
>>> by many other people.
>> 
>> To that end, if you're able to use a gnu C library (glibc),
>> there's tree, hash and binary search capabilities available
>> using 'tsearch et. alia', 'bsearch et. alia' and 'hsearch et alia'.
>> 
>
>And to meet the 'self contained' requirement, you just need to add the 
>library source code to your project (and follow the licensing restrictions)

Or you could just target linux.  :-)

[toc] | [prev] | [next] | [standalone]

#150157

From	already5chosen@yahoo.com
Date	2020-02-22 10:33 -0800
Message-ID	<60a031e2-c063-42a7-a0e9-f478eea49ca3@googlegroups.com>
In reply to	#150133

On Saturday, February 22, 2020 at 1:41:19 AM UTC+2, Richard Damon wrote:
> On 2/21/20 6:23 PM, Scott Lurndal wrote:
> > James Kuyper <jameskuyper@alumni.caltech.edu> writes:
> >> Scott Lurndal wrote:
> >>> In the several days this discussion has been in process,
> > 
> >>
> >> Not particularly. So long as it's not significantly slower
> >> than the algorithm it will be replacing (which uses C++ and
> >> std::map<>), I should be fine - I just want to be sure that
> >> it will be no slower. I'm primarily interested in ease of
> >> implementation. The Subject of this thread was chosen to
> >> express my annoyance at having to reimplement something
> >> that has been implemented and thoroughly tested many times
> >> by many other people.
> > 
> > To that end, if you're able to use a gnu C library (glibc),
> > there's tree, hash and binary search capabilities available
> > using 'tsearch et. alia', 'bsearch et. alia' and 'hsearch et alia'.
> > 
> 
> And to meet the 'self contained' requirement, you just need to add the 
> library source code to your project (and follow the licensing restrictions)

In case of glibc, I think that using it in source form will turn its license from LGPL into something like GPL2, if not GPL3.
I don't know if it is acceptable for James's project, but would guess that the answer is "No".

Anyway, glibc hash support is ASCIIZ string-oriented. Of course, it is possible to convert a pair of 16-bit signed integers to ASCIIZ, but it's unlikely that it would be great for performance.
And the absence of control over hash function algorithm means that one can't optimize it for a common case.

[toc] | [prev] | [next] | [standalone]

#150162

From	James Kuyper <jameskuyper@alumni.caltech.edu>
Date	2020-02-22 15:00 -0500
Message-ID	<r2s194$bhr$1@dont-email.me>
In reply to	#150157

On 2/22/20 1:33 PM, already5chosen@yahoo.com wrote:
> On Saturday, February 22, 2020 at 1:41:19 AM UTC+2, Richard Damon wrote:
>> On 2/21/20 6:23 PM, Scott Lurndal wrote:
...
>>> To that end, if you're able to use a gnu C library (glibc),
>>> there's tree, hash and binary search capabilities available
>>> using 'tsearch et. alia', 'bsearch et. alia' and 'hsearch et alia'.
>>>
>>
>> And to meet the 'self contained' requirement, you just need to add the 
>> library source code to your project (and follow the licensing restrictions)
> 
> In case of glibc, I think that using it in source form will turn its license from LGPL into something like GPL2, if not GPL3.
> I don't know if it is acceptable for James's project, but would guess that the answer is "No".

I'll ask about that issue on Monday.

> Anyway, glibc hash support is ASCIIZ string-oriented. Of course, it is possible to convert a pair of 16-bit signed integers to ASCIIZ, but it's unlikely that it would be great for performance.
> And the absence of control over hash function algorithm means that one can't optimize it for a common case.

I can sprintf() the numbers to create a key usable with hsearch() - a
little inefficient, but feasible.

[toc] | [prev] | [next] | [standalone]

#150163

From	Richard Damon <Richard@Damon-Family.org>
Date	2020-02-22 15:16 -0500
Message-ID	<Y_f4G.203450$Up2.106967@fx44.iad>
In reply to	#150157

On 2/22/20 1:33 PM, already5chosen@yahoo.com wrote:
> On Saturday, February 22, 2020 at 1:41:19 AM UTC+2, Richard Damon wrote:
>> On 2/21/20 6:23 PM, Scott Lurndal wrote:
>>> James Kuyper <jameskuyper@alumni.caltech.edu> writes:
>>>> Scott Lurndal wrote:
>>>>> In the several days this discussion has been in process,
>>>
>>>>
>>>> Not particularly. So long as it's not significantly slower
>>>> than the algorithm it will be replacing (which uses C++ and
>>>> std::map<>), I should be fine - I just want to be sure that
>>>> it will be no slower. I'm primarily interested in ease of
>>>> implementation. The Subject of this thread was chosen to
>>>> express my annoyance at having to reimplement something
>>>> that has been implemented and thoroughly tested many times
>>>> by many other people.
>>>
>>> To that end, if you're able to use a gnu C library (glibc),
>>> there's tree, hash and binary search capabilities available
>>> using 'tsearch et. alia', 'bsearch et. alia' and 'hsearch et alia'.
>>>
>>
>> And to meet the 'self contained' requirement, you just need to add the
>> library source code to your project (and follow the licensing restrictions)
> 
> In case of glibc, I think that using it in source form will turn its license from LGPL into something like GPL2, if not GPL3.
> I don't know if it is acceptable for James's project, but would guess that the answer is "No".
> 
> Anyway, glibc hash support is ASCIIZ string-oriented. Of course, it is possible to convert a pair of 16-bit signed integers to ASCIIZ, but it's unlikely that it would be great for performance.
> And the absence of control over hash function algorithm means that one can't optimize it for a common case.
> 

One reason I included the comment. It may still be possible to be able 
to use the 'out' of LGPL if even though the source code is in the 
project tree, it is separately built and linked into the code in a 
manner conforming to the LGPL license.

The GPL 'infection' also could be used as ammo to talk to the PHB that 
added the 'self-contained' requirement and ask if it REALLY is needed.

[toc] | [prev] | [next] | [standalone]

#150126

From	James Kuyper <jameskuyper@alumni.caltech.edu>
Date	2020-02-21 08:42 -0800
Message-ID	<2c8f157b-f388-4aa5-9c65-1bd4fd552d6d@googlegroups.com>
In reply to	#150118

Well, I'll have to walk back almost everything I said in my previous
message. Annoying.

First of all, x-y isn't a perfect hash. I was ignoring (and therefore
didn't mention) the fact that the x axis wraps around, such that for
most values of y, the point immediately to the left of (0,y) is the
point (0x9FFF,y). As a result, for any negative value of x-y, there
could be two different points with the same value of x-y on the list.
Still, that's almost as good as a perfect hash. However, there's also a
small number of special cases where there could be a third one.

Secondly, while my algorithm should require a significantly shorter list
of points than the one it will replace, my reasons for believing that
the list would be logarithmcly smaller were fallacious. My new estimate
of the maximum number of points, after correcting both of these errors,
is now about 50% higher than my first estimate.

Thirdly, I've been concentrating on a set of special cases that happen
to be easy to handle. I did that because those cases will be the most
common ones. However, for the immediate future, in the absolute worst
case there could be nearly 4 million points on the list, and nearly 800
different points with the same value for x-y. Future development could
increase those numbers to 300 million and 6000, respectively. The easy
special cases are capable of evolving into the worst case, so the
solution I use for the easy cases must also be compatible with an
acceptable solution for the worst case. Any hash function I use would
have to be a function of x and y.

The worst case involves a very large number of points that are evenly
distributed over all possible x,y pairs.
In realistic cases, the number of points on the list will be much
smaller, and much less evenly distributed. The n least significant bits
of x and y are disproportionately likely to be exactly 0, with the same
value of n for both x and y, but with different values of n for
different points. The points will tend to trace out closed curves - in
other words, for any given point on the list, there will generally be
two other points on the list that differ from it in either the x value
or the y value, or both, by 2^(n+1) or less.
In the simple cases, n will be a constant for all points, and, nearly
one third of the points will all have an x value of exactly 0.
Whatever method I use to keep track of that list should be optimized for
realistic cases, without getting bogged down in the worst case, and
without handling the simple common cases too inefficiently.

[toc] | [prev] | [next] | [standalone]

#150128

From	David Brown <david.brown@hesbynett.no>
Date	2020-02-21 18:23 +0100
Message-ID	<r2p3mj$n1u$2@dont-email.me>
In reply to	#150126

On 21/02/2020 17:42, James Kuyper wrote:
> Well, I'll have to walk back almost everything I said in my previous
> message. Annoying.
> 

Don't get annoyed about this.  View it as gaining a better understanding 
of the problem.  There is nothing like trying to explain a problem to 
others for gaining more insight yourself.

[toc] | [prev] | [next] | [standalone]

#150166

From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Date	2020-02-22 17:06 -0800
Message-ID	<86o8tqaz8q.fsf@linuxsc.com>
In reply to	#150099

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.

[toc] | [prev] | [next] | [standalone]

#150184

From	James Kuyper <jameskuyper@alumni.caltech.edu>
Date	2020-02-23 06:18 -0800
Message-ID	<19b907bc-039b-48ad-baac-54127f72921a@googlegroups.com>
In reply to	#150166

On Saturday, February 22, 2020 at 8:06:42 PM UTC-5, Tim Rentsch wrote:
> 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.

Thank you. I've been writing my own implementation of a hash table, but
it would be good to have one that has already been written and tested to
compare mine with; I'm sure my implementation currently has defects and
missing features.

[toc] | [prev] | [next] | [standalone]

#150102

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2020-02-20 21:14 +0000
Message-ID	<87o8ttarlc.fsf@bsb.me.uk>
In reply to	#150093

James Kuyper <jameskuyper@alumni.caltech.edu> writes:
<cut>
> There's a key that I can easily calculate that uniquely identifies each
> value, so one approach would be
>
> Compute key
> Search for key in a key-location list
> IF found THEN
> Retrieve previously calculated value from the corresponding location
> Remove key-location pair from list
> ELSE
> Calculate new value
> Allocate storage
> Store that value in that location.
> Add the key-location pair to the list
> ENDIF
>
> In the worst case, my code will be generating on the order of
> 2^18 different values, but that list should never need to
> store more than about 2^9 key-location pairs (possible future
> developments might increase those values to 2^31 and 2^16,
> respectively).
>
> What kind of data structure would you recommend for storing that list of
> key-location pairs?

2^9 is tiny and 2^16 is not large (I think if you had 64K for code and
data combined you'd have mentioned that!) so you should be able to avoid
the parts that make a hash table fussy -- changing the size and
re-hashing everything.  Pre-allocating the table at, say, three times
the maximum occupancy and using the simplest open addressing would make
the code short and sweet.

Is there any pattern to the keys, and to the order in which they crop
up, that might be exploited to make the code even simpler?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#150119

From	James Kuyper <jameskuyper@alumni.caltech.edu>
Date	2020-02-21 00:24 -0500
Message-ID	<r2nphv$h7i$1@dont-email.me>
In reply to	#150102

On 2/20/20 4:14 PM, Ben Bacarisse wrote:
> James Kuyper <jameskuyper@alumni.caltech.edu> writes:
> <cut>
>> There's a key that I can easily calculate that uniquely identifies each
>> value, so one approach would be
>>
>> Compute key
>> Search for key in a key-location list
>> IF found THEN
>> Retrieve previously calculated value from the corresponding location
>> Remove key-location pair from list
>> ELSE
>> Calculate new value
>> Allocate storage
>> Store that value in that location.
>> Add the key-location pair to the list
>> ENDIF
>>
>> In the worst case, my code will be generating on the order of
>> 2^18 different values, but that list should never need to
>> store more than about 2^9 key-location pairs (possible future
>> developments might increase those values to 2^31 and 2^16,
>> respectively).
>>
>> What kind of data structure would you recommend for storing that list of
>> key-location pairs?
> 
> 2^9 is tiny and 2^16 is not large (I think if you had 64K for code and
> data combined you'd have mentioned that!) so you should be able to avoid
> the parts that make a hash table fussy -- changing the size and
> re-hashing everything.  Pre-allocating the table at, say, three times
> the maximum occupancy and using the simplest open addressing would make
> the code short and sweet.
> 
> Is there any pattern to the keys, and to the order in which they crop
> up, that might be exploited to make the code even simpler?

There is very definitely a pattern. It's a complicated one, but in
principle it should be possible to calculate whether a given point is
being processed for the first or second time, and even to calculate what
location it was stored in the first time, when processing it the second
time - but in practice it's not at all clear how to perform those
calculations.

However, I realized today that the pattern does have some simple
properties that can be used to greatly simplify the search. See my
response to already5chosen for more details.

[toc] | [prev] | [next] | [standalone]

#150103

From	"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date	2020-02-20 13:15 -0800
Message-ID	<r2mst0$nhk$3@gioia.aioe.org>
In reply to	#150093

On 2/20/2020 10:33 AM, James Kuyper wrote:
> It's reinventing the wheel time, again.
[...]
> What kind of data structure would you recommend for storing that list of
> key-location pairs?
> 

Maybe, a Judy Array? Sorry if this is way off base. I need to read your 
post on a deeper level.

[toc] | [prev] | [next] | [standalone]

#150108

From	James Kuyper <jameskuyper@alumni.caltech.edu>
Date	2020-02-20 13:44 -0800
Message-ID	<60aeb6ae-d9d5-42b9-9a0c-3ea1f1898f61@googlegroups.com>
In reply to	#150103

According to the Wikipedia article, "In most applications the
possible performance advantage [of using a Judy array] is too
small to justify the high complexity of the data structure
implementation." I'm fairly sure that applies to my case.

[toc] | [prev] | [next] | [standalone]

#150112

From	"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date	2020-02-20 14:21 -0800
Message-ID	<r2n0or$19jc$1@gioia.aioe.org>
In reply to	#150108

On 2/20/2020 1:44 PM, James Kuyper wrote:
> According to the Wikipedia article, "In most applications the
> possible performance advantage [of using a Judy array] is too
> small to justify the high complexity of the data structure
> implementation." I'm fairly sure that applies to my case.
> 

Okay. For some strange reason I am thinking about a hash based LRU. 
Still reading your requirements.

[toc] | [prev] | [next] | [standalone]

#150115

From	"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date	2020-02-20 14:22 -0800
Message-ID	<r2n0r2$19jc$2@gioia.aioe.org>
In reply to	#150112

On 2/20/2020 2:21 PM, Chris M. Thomasson wrote:
> On 2/20/2020 1:44 PM, James Kuyper wrote:
>> According to the Wikipedia article, "In most applications the
>> possible performance advantage [of using a Judy array] is too
>> small to justify the high complexity of the data structure
>> implementation." I'm fairly sure that applies to my case.
>>
> 
> Okay. For some strange reason I am thinking about a hash based LRU. 
> Still reading your requirements.

A simple hash into buckets that have doubly linked lists? Or even hash 
into a bucket with another vector that can be hashed into again, then we 
finally hit the dynamic part.

[toc] | [prev] | [next] | [standalone]

#150104

From	Robert Wessel <robertwessel2@yahoo.com>
Date	2020-02-20 15:19 -0600
Message-ID	<0mtt4f11chm1b6uo1pdjdm4kc8vbop2ln7@4ax.com>
In reply to	#150093

On Thu, 20 Feb 2020 10:33:01 -0800 (PST), James Kuyper
<jameskuyper@alumni.caltech.edu> wrote:

>It's reinventing the wheel time, again.
>
>I have some code I need to write, with the externally imposed
>requirement that it be written in C and be self-contained. That is, it
>must not reference any external libraries other than the C standard
>library. If I could use C++, I'd use std::map<> to solve the problem
>described below, and even in C there's many widely available third-party
>libraries I could use to similar effect. Because those alternatives are
>normally available, the last time I had to implement any such algorithm
>was about 30 years ago. My BS was in Physics, not CS, so I never did a
>formal study of such algorithms. Therefore, I'm looking for advice as to
>the best algorithm to use, and ideally public-domain source code I could
>copy and modify as needed. Efficiency is the key thing I'm looking for,
>but keep in mind that std::map<> would have been acceptably efficient,
>if I could have used it. Since I'm going to have to write, understand,
>and test the code, simplicity of implementation is also important.
>
>My code will be computing a large number of values, and will unavoidably
>have to deal with each value exactly twice. It would be nice to avoid
>calculating each value twice, but the computation time isn't large
>enough for that to be a significant issue. The main problem is that I
>need to store each value exactly once.
>
>There's a key that I can easily calculate that uniquely identifies each
>value, so one approach would be
>
>Compute key
>Search for key in a key-location list
>IF found THEN
>Retrieve previously calculated value from the corresponding location
>Remove key-location pair from list
>ELSE
>Calculate new value
>Allocate storage
>Store that value in that location.
>Add the key-location pair to the list
>ENDIF
>
>In the worst case, my code will be generating on the order of
>2^18 different values, but that list should never need to
>store more than about 2^9 key-location pairs (possible future
>developments might increase those values to 2^31 and 2^16,
>respectively).
>
>What kind of data structure would you recommend for storing that list of
>key-location pairs?


A hash table with separate chaining is my first thought.  Especially
if you can either estimate the number of items, or do the first pass
without needing lookups.

You need the table of root pointers, and only link field in each item.
You size the root pointers based on the number of (linear) search
steps you want to do on average (if there a N items, and you want the
average chain to be about 4 items, N/4).  If you can't produce an
estimate, you can just do the entire first pass, dumping all the items
into a linked list, and then allocate the root table and hash all the
entries after the pass.

[toc] | [prev] | [next] | [standalone]

#150120

From	James Kuyper <jameskuyper@alumni.caltech.edu>
Date	2020-02-21 00:28 -0500
Message-ID	<r2nppi$if9$1@dont-email.me>
In reply to	#150104

On 2/20/20 4:19 PM, Robert Wessel wrote:
> On Thu, 20 Feb 2020 10:33:01 -0800 (PST), James Kuyper
> <jameskuyper@alumni.caltech.edu> wrote:
> 
>> It's reinventing the wheel time, again.
>>
>> I have some code I need to write, with the externally imposed
>> requirement that it be written in C and be self-contained. That is, it
>> must not reference any external libraries other than the C standard
>> library. If I could use C++, I'd use std::map<> to solve the problem
>> described below, and even in C there's many widely available third-party
>> libraries I could use to similar effect. Because those alternatives are
>> normally available, the last time I had to implement any such algorithm
>> was about 30 years ago. My BS was in Physics, not CS, so I never did a
>> formal study of such algorithms. Therefore, I'm looking for advice as to
>> the best algorithm to use, and ideally public-domain source code I could
>> copy and modify as needed. Efficiency is the key thing I'm looking for,
>> but keep in mind that std::map<> would have been acceptably efficient,
>> if I could have used it. Since I'm going to have to write, understand,
>> and test the code, simplicity of implementation is also important.
>>
>> My code will be computing a large number of values, and will unavoidably
>> have to deal with each value exactly twice. It would be nice to avoid
>> calculating each value twice, but the computation time isn't large
>> enough for that to be a significant issue. The main problem is that I
>> need to store each value exactly once.
>>
>> There's a key that I can easily calculate that uniquely identifies each
>> value, so one approach would be
>>
>> Compute key
>> Search for key in a key-location list
>> IF found THEN
>> Retrieve previously calculated value from the corresponding location
>> Remove key-location pair from list
>> ELSE
>> Calculate new value
>> Allocate storage
>> Store that value in that location.
>> Add the key-location pair to the list
>> ENDIF
>>
>> In the worst case, my code will be generating on the order of
>> 2^18 different values, but that list should never need to
>> store more than about 2^9 key-location pairs (possible future
>> developments might increase those values to 2^31 and 2^16,
>> respectively).
>>
>> What kind of data structure would you recommend for storing that list of
>> key-location pairs?
> 
> 
> A hash table with separate chaining is my first thought.  Especially
> if you can either estimate the number of items, or do the first pass
> without needing lookups.
> 
> You need the table of root pointers, and only link field in each item.
> You size the root pointers based on the number of (linear) search
> steps you want to do on average (if there a N items, and you want the
> average chain to be about 4 items, N/4).  If you can't produce an
> estimate, you can just do the entire first pass, dumping all the items
> into a linked list, and then allocate the root table and hash all the
> entries after the pass.
> 

Features of my algorithm that I didn't notice, and therefore didn't
explain, turn out to make a hash table overkill for this problem. See my
response to already5chosen for more details.

[toc] | [prev] | [next] | [standalone]

#150121

From	"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date	2020-02-20 23:27 -0800
Message-ID	<r2o0pr$1jub$1@gioia.aioe.org>
In reply to	#150093

On 2/20/2020 10:33 AM, James Kuyper wrote:
> It's reinventing the wheel time, again.
[...]
> What kind of data structure would you recommend for storing that list of
> key-location pairs?
> 

Think out loud here, sorry, but you might be able to benefit from a 
pairing function:

https://en.wikipedia.org/wiki/Pairing_function

Humm... The numbers can get large.

Pairing 2^9 with 2^9 = 525312
____________________
#include <stdio.h>
#include <assert.h>


unsigned long
ct_cantor_pair(
     unsigned long p0,
     unsigned long p1
) {
     unsigned long pair = (p0 + p1) * (p0 + p1 + 1) / 2 + p1;

     return pair;
}


int main(void)
{
     {
         unsigned long pair = ct_cantor_pair(512, 512);

         printf("pair = %lu\n", pair);
     }

     {
         printf("\n\nFin!\n");
         fflush(stdout);
         getchar();
     }

     return 0;
}
____________________

[toc] | [prev] | [next] | [standalone]

#150122

From	"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date	2020-02-20 23:52 -0800
Message-ID	<r2o279$1q1u$1@gioia.aioe.org>
In reply to	#150121

On 2/20/2020 11:27 PM, Chris M. Thomasson wrote:
> On 2/20/2020 10:33 AM, James Kuyper wrote:
>> It's reinventing the wheel time, again.
> [...]
>> What kind of data structure would you recommend for storing that list of
>> key-location pairs?
>>
> 
> Think out loud here, sorry, but you might be able to benefit from a 
> pairing function:
> 
> https://en.wikipedia.org/wiki/Pairing_function
> 
> Humm... The numbers can get large.
> 
> Pairing 2^9 with 2^9 = 525312
[...]

Fwiw, here is a sample program that pairs and depairs values, it acts 
like a hash wrt storing two values in a single value:
_______________________
#include <stdio.h>
#include <assert.h>
#include <math.h>


struct ct_entry
{
     unsigned long value;
     unsigned long key;
};


unsigned long
ct_cantor_inpair(
     struct ct_entry entry
) {
     unsigned long pair = (entry.value + entry.key) * (entry.value + 
entry.key + 1) / 2 + entry.key;

     return pair;
}


struct ct_entry
ct_cantor_depair(
     unsigned long value
) {
     struct ct_entry entry = { 0, 0 };

     unsigned long p0 = (sqrt((8 * value) + 1) - 1) / 2;
     unsigned long p1 = value - ((p0 * (p0 + 1)) / 2);

     entry.value = p0 - p1;
     entry.key = p1;

     return entry;
}


int main(void)
{
     {

         struct ct_entry entry = { 512, 512 };

         printf("entry.value = %lu\n", entry.value);
         printf("entry.key = %lu\n\n", entry.key);

         unsigned long pair = ct_cantor_inpair(entry);
         printf("pair = %lu\n\n", pair);

         struct ct_entry depair = ct_cantor_depair(pair);

         printf("depair.value = %lu\n", depair.value);
         printf("depair.key = %lu\n", depair.key);
     }

     {
         printf("\n\nFin!\n");
         fflush(stdout);
         getchar();
     }

     return 0;
}
_______________________

Is this of any use to you at all?

[toc] | [prev] | [next] | [standalone]

#150125

From	jadill33@gmail.com
Date	2020-02-21 08:20 -0800
Message-ID	<5d45520f-152f-43e2-9b0c-2a5f8e80c412@googlegroups.com>
In reply to	#150093

On Thursday, February 20, 2020 at 1:33:10 PM UTC-5, James Kuyper wrote:
> It's reinventing the wheel time, again.
> 
> I have some code I need to write, with the externally imposed
> requirement that it be written in C and be self-contained. That is, it
> must not reference any external libraries other than the C standard
> library. If I could use C++, I'd use std::map<> to solve the problem
> described below, and even in C there's many widely available third-party
> libraries I could use to similar effect. Because those alternatives are
> normally available, the last time I had to implement any such algorithm
> was about 30 years ago. My BS was in Physics, not CS, so I never did a
> formal study of such algorithms. Therefore, I'm looking for advice as to
> the best algorithm to use, and ideally public-domain source code I could
> copy and modify as needed. Efficiency is the key thing I'm looking for,
> but keep in mind that std::map<> would have been acceptably efficient,
> if I could have used it. Since I'm going to have to write, understand,
> and test the code, simplicity of implementation is also important.
> 
> My code will be computing a large number of values, and will unavoidably
> have to deal with each value exactly twice. It would be nice to avoid
> calculating each value twice, but the computation time isn't large
> enough for that to be a significant issue. The main problem is that I
> need to store each value exactly once.
> 
> There's a key that I can easily calculate that uniquely identifies each
> value, so one approach would be
> 
> Compute key
> Search for key in a key-location list
> IF found THEN
> Retrieve previously calculated value from the corresponding location
> Remove key-location pair from list
> ELSE
> Calculate new value
> Allocate storage
> Store that value in that location.
> Add the key-location pair to the list
> ENDIF
> 
> In the worst case, my code will be generating on the order of
> 2^18 different values, but that list should never need to
> store more than about 2^9 key-location pairs (possible future
> developments might increase those values to 2^31 and 2^16,
> respectively).
> 
> What kind of data structure would you recommend for storing that list of
> key-location pairs?

If you want my quick and dirty, if you already have a perfect hash for each
of the objects, and memory is not an issue (from below, I see that you're
storing 3-double sized blocks, that's 2^18 * 3 * sizeof double, or roughly
6 MB assuming sizeof double of 8).  I presume that this would be on a workstation that has some decent amount of RAM, so allocating 6 MB array for
an algorithm I wouldn't think would be a big deal on a workstations that
often run upwards of 16GB.  This would likely be pretty fast and gives you
a metric to compare against.

If you upscale to your future requirements, that array would be on the order
of 2^31 * 3 * sizeof double which is about 50GB of RAM.  You're probably
getting uncomfortable allocating that size of a flat array.  At this point,
I think it makes more sense to use a hash table of some kind, and as you
constrain memory, you may start getting collisions.  My preference for this
kind of thing is a hash table with double linked list buckets, since it
seems that item removal is a possibility, seems better than the open
addressing.

I recommend getting it working with a large allocated array first.  It's
likely simple to implement, and provides a benchmark to compare against
for both speed and correctness when you implement your data structure
version.  Then once you get the data structure version, you can try to
scale your algorithm size up and see the relative performance comparisons
(start with 2^18, 2^19, 2^20, and so on).  You can allocate list nodes
and the bucket array using the standard allocator.

If you need to start constraining memory but still want to maximize
performance, you may want to try to maximize memory locality of the hash
table list node elements.  This usually involves some kind of fixed object
allocator where you allocate a chunk of list node objects and then assign
allocation from unused objects in that pool.  On deletion, you can recycle
the block or you can use a more hacky "never use" bit to permanently delete
that location.  You can daisy chain those chunks together as you need more
nodes as your pool size grows.

For example, if each list node consists of 2 pointers and 3 doubles, on a
64-bit system, that's looking at 40-byte objects that you can allocate from
a pool (let's say that we use page size of 4K).  So you can allocate a slab
of 4096 / 40 or 102 list node objects in a pool, then pull from that pool as
necessary.  If you need more than 102 objects, allocate another slab of 102
objects from the next page, and daisy chain them together when you search for
the next free node.

At this point, you're doing a hacked version of the kind of work that malloc
does, but you're able to enforce the locality, which may provide better
performance.  This is the other side of the spectrum, where you're maximizing
developer effort to try to get the best performance in terms of memory and
speed.

Not sure if it's that helpful, but that's my first impression.

Best regards,
John D.

[toc] | [prev] | [next] | [standalone]

#150141

From	Malcolm McLean <malcolm.arthur.mclean@gmail.com>
Date	2020-02-22 03:15 -0800
Message-ID	<28c6d89d-1439-477a-ba1a-6d694deec7a1@googlegroups.com>
In reply to	#150093

On Thursday, 20 February 2020 18:33:10 UTC, James Kuyper  wrote:
> It's reinventing the wheel time, again.
> 
> I have some code I need to write, with the externally imposed
> requirement that it be written in C and be self-contained. That is, it
> must not reference any external libraries other than the C standard
> library. If I could use C++, I'd use std::map<> to solve the problem
> described below, and even in C there's many widely available third-party
> libraries I could use to similar effect. Because those alternatives are
> normally available, the last time I had to implement any such algorithm
> was about 30 years ago. My BS was in Physics, not CS, so I never did a
> formal study of such algorithms. Therefore, I'm looking for advice as to
> the best algorithm to use, and ideally public-domain source code I could
> copy and modify as needed. Efficiency is the key thing I'm looking for,
> but keep in mind that std::map<> would have been acceptably efficient,
> if I could have used it. Since I'm going to have to write, understand,
> and test the code, simplicity of implementation is also important.
> 
> What kind of data structure would you recommend for storing that list of
> key-location pairs?

Dust off your copy of Basic Algorithms and take the red black tree. 
(The code used to be online but the provider has now gone defunct).

[toc] | [prev] | [next] | [standalone]

Page 2 of 4 — ← Prev page 1 [2] 3 4 Next page →

csiph-web

Reinventing the wheel.

Contents

#150149

#150157

#150162

#150163

#150126

#150128

#150166

#150184

#150102

#150119

#150103

#150108

#150112

#150115

#150104

#150120

#150121

#150122

#150125

#150141