Re: GLib source id wrap around

[Owen Taylor <otaylor redhat com>]

On Sat, 2003-10-25 at 17:50, Soeren Sandmann wrote:
> Owen Taylor <otaylor redhat com> writes:
> 
> > storing all used IDs in a sorted data structure is possible, but
> > expensive.
> 
> I occured to me that this can be done using just two bits per stored
> ID. The data structure is a binary tree storing all numbers in a range
> [0, 2^k - 1], like this one for the range [0, 15]:
>
>                        .
>                .               .
>            .       .       .       .
>          .   .   .   .   .   .   .   .
>         . . . . . . . . . . . . . . . .
>         0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1
>                             0 1 2 3 4 5
> 
> 
> Each dot in the tree is a bit meaning
> 
>         TRUE, all leaves below me are used 
>         FALSE, there is at least one unused leaf below me

Neat idea. You can do a bit better by:

 A) Making on bits mean free, not used
 B) Making the tree be a tree on 32-bit words, not bits

If you do that, the parent is just the bitwise OR of the children.

But even so, it's pretty hard to beat a simple linear bit-array;
it may be O(n) but it's O(n) with a really low prefactor. Fooling
around with the attached indicates that the cross-over where
the tree is faster is at several thousand active IDs.

Regards,
						Owen



#include <glib.h>
#include <string.h>

typedef struct _GIDAllocator GIDAllocator;

struct _GIDAllocator
{
  guint n_words;
  guint32 *data;
};

#define INITIAL_WORDS 4

GIDAllocator *
g_id_allocator_new (void)
{
  GIDAllocator *allocator = g_new (GIDAllocator, 1);

  allocator->n_words = INITIAL_WORDS;
  allocator->data = g_new (guint32, INITIAL_WORDS);
  memset (allocator->data, 0xff, INITIAL_WORDS * sizeof (guint32));
      
  return allocator;
}

void
g_id_allocator_free (GIDAllocator *allocator)
{
  g_free (allocator->data);
  g_free (allocator);
}

static inline gint
first_set_bit (guint32 word)
{
  static const char table[16] = {
    4, 0, 1, 0,
    2, 0, 1, 0,
    3, 0, 1, 0,
    2, 0, 1, 0
  };

  gint result = 0;
  
  if ((word & 0xffff) == 0)
    {
      word >>= 16;
      result += 16;
    }

  if ((word & 0xff) == 0)
    {
      word >>= 8;
      result += 8;
    }

  if ((word & 0xf) == 0)
    {
      word >>= 4;
      result += 4;
    }

  return result + table[word & 0xf];
}


guint
g_id_allocator_alloc (GIDAllocator *allocator)
{
  guint i;

  for (i = 0; i < allocator->n_words; i++)
    {
      if (allocator->data[i] != 0)
	{
	  gint free_bit = first_set_bit (allocator->data[i]);
	  allocator->data[i] &= ~(1 << free_bit);

	  return 32 * i + free_bit;
	}
    }

  {
    guint n_words = allocator->n_words;
    
    allocator->data = g_renew (guint32, allocator->data, n_words * 2);
    memset (&allocator->data[n_words], 0xff, n_words * sizeof (guint32));
    allocator->n_words = n_words * 2;
    
    allocator->data[n_words] = 0xffffffff - 1;
    
    return 32 * n_words;
  }
}

void
g_id_allocator_release (GIDAllocator *allocator,
			guint         id)
{
  allocator->data[id >> 5] |= 1 << (id & 31);
}

int main (int argc, char **argv)
{
  GIDAllocator *allocator = g_id_allocator_new ();
  guint i;
  guint iter;

  for (i = 0; i < 1000; i++)
    {
      guint id = g_id_allocator_alloc (allocator);
      g_assert (id == i);
    }
  
  for (i = 0; i < 1000; i++)
    g_id_allocator_release (allocator, i);

  for (iter = 0; iter < 10000; iter++)
    {
      for (i = 0; i < 1000; i++)
	g_id_allocator_alloc (allocator);
      
      for (i = 0; i < 1000; i++)
	g_id_allocator_release (allocator, i);
    }

  g_id_allocator_free (allocator);

  return 0;
}

#include <glib.h>
#include <string.h>

typedef struct _GIDAllocator GIDAllocator;

struct _GIDAllocator
{
  guint levels;
  guint n_words;
  guint32 *data;
};

#define INITIAL_WORDS 4
#define INITIAL_LEVELS 1;

GIDAllocator *
g_id_allocator_new (void)
{
  GIDAllocator *allocator = g_new (GIDAllocator, 1);

  allocator->n_words = INITIAL_WORDS;
  allocator->levels = INITIAL_LEVELS;
  allocator->data = g_new (guint32, INITIAL_WORDS);
  memset (allocator->data, 0xff, INITIAL_WORDS * sizeof (guint32));
      
  return allocator;
}

void
g_id_allocator_free (GIDAllocator *allocator)
{
  g_free (allocator->data);
  g_free (allocator);
}

static inline gint
first_set_bit (guint32 word)
{
  static const char table[16] = {
    4, 0, 1, 0,
    2, 0, 1, 0,
    3, 0, 1, 0,
    2, 0, 1, 0
  };

  gint result = 0;
  
  if ((word & 0xffff) == 0)
    {
      word >>= 16;
      result += 16;
    }

  if ((word & 0xff) == 0)
    {
      word >>= 8;
      result += 8;
    }

  if ((word & 0xf) == 0)
    {
      word >>= 4;
      result += 4;
    }

  return result + table[word & 0xf];
}

static void
dump (GIDAllocator *allocator)
{
  guint i;
  for (i = 0; i < allocator->n_words - 1; i++)
    g_print ("%x ", allocator->data[i]);

  g_print ("\n");
}

guint
g_id_allocator_alloc (GIDAllocator *allocator)
{
  if (allocator->data[0] != 0)
    {
      gint i;
      guint index = 0;
      guint result;
      gint first_bit;
      guint mask;

      for (i = allocator->levels; i; i--)
	{
	  guint index1 = index * 2 + 1;
	  guint index2 = index * 2 + 2;
	  
	  index = (allocator->data[index1] != 0) ? index1 : index2;
	}

      first_bit = first_set_bit (allocator->data[index]);
      mask = allocator->data[index] & ~(1 << first_bit);
      allocator->data[index] = mask;

      result = (index - (allocator->n_words / 2 - 1)) * 32 + first_bit;

      for (i = allocator->levels; i; i--)
	{
	  guint other = index - 1 + 2 * (index & 1);
	  mask |= allocator->data[other];

	  index = (index - 1) / 2;
	  allocator->data[index] = mask;
	}

      return result;
    }
  else
    {
      guint start, step;
      gint i;

      allocator->levels ++;
      allocator->n_words *= 2;

      g_free (allocator->data);
      allocator->data = g_malloc0 (allocator->n_words * sizeof (guint32));
      allocator->data[0] = 0xffffffff;

      start = 1;
      step = 1;
      for (i = allocator->levels; i; i--)
	{
	  memset (&allocator->data[start], 0, step * sizeof (guint32));
	  memset (&allocator->data[start + step], 0xff, step * sizeof (guint32));

	  start += step * 2;
	  step = step * 2;
	}

      allocator->data[allocator->n_words / 2 + allocator->n_words / 4 - 1] = 0xffffffff - 1;

      return (allocator->n_words / 4) * 32;
    }
}

void
g_id_allocator_release (GIDAllocator *allocator,
			guint         id)
{
  guint index = id / 32 + allocator->n_words / 2 - 1;
  guint mask;
  gint i;
  
  mask = allocator->data[index] | (1 << (id & 31));
  allocator->data[index] = mask;

  for (i = allocator->levels; i; i--)
    {
      guint other = index - 1 + 2 * (index & 1);
      mask |= allocator->data[other];
      
      index = (index - 1) / 2;
      allocator->data[index] = mask;
    }
}

int main (int argc, char **argv)
{
  GIDAllocator *allocator = g_id_allocator_new ();
  guint i;
  guint iter;

  for (i = 0; i < 1000; i++)
    {
      guint id = g_id_allocator_alloc (allocator);
      g_assert (id == i);
    }

  for (i = 0; i < 1000; i++)
    g_id_allocator_release (allocator, i);

  for (iter = 0; iter < 10000; iter++)
    {
      for (i = 0; i < 1000; i++)
	g_id_allocator_alloc (allocator);
      
      for (i = 0; i < 1000; i++)
	g_id_allocator_release (allocator, i);
    }

  g_id_allocator_free (allocator);

  return 0;
}