g_list_append is O(n^2)

[Robert Wilhelm <robert physiol med tu-muenchen de>]

g_list_append() does not work in linear time as it is required for the STL
equivalent.


Robert


================================================================================

#include <glib.h>
#include <stdio.h>
#include <list>

// time stamp counter on pentium
inline unsigned long long get_ticks(void)
{
  unsigned long high, low;
  
  __asm__ __volatile__(".byte 0x0f,0x31"
		       : "=a" (low), "=d" (high));
  return ((unsigned long long) high << 32) + low;
}

stl()
{
  unsigned long long t;

  int i,j;
  list<void *> L;
  for(i=0;i<20;i++)
    {
      t = get_ticks();
      for(j=0;j<1000;j++)
	{
	  L.insert(L.end(),NULL);
	}
      printf("%d %lld\n",i,get_ticks()-t);
    }
}


glib()
{
  unsigned long long t;

  int i,j;
  GList *list = NULL;
  for(i=0;i<20;i++)
    {
      t = get_ticks();
      for(j=0;j<1000;j++)
	{
	  list = g_list_append(list,NULL);
	}
      printf("%d %lld\n",i,get_ticks()-t);
    }
}

int main()
{
  glib();
  stl();

  return 0;
}

==================================================================
0 2581728
1 9178682
2 15185730
3 21064790
4 26974204
5 32957790
6 39017079
7 45455470
8 51272079
9 58683256
10 65666256
11 101009012
12 120725100
13 169410800
14 202480634
15 224454207
16 243811552
17 270931437
18 306276677
19 317826777
0 279237
1 280151
2 280803
3 272187
4 289467
5 277634
6 287829
7 290691
8 282312
9 289397
10 289966
11 291964
12 291761
13 288551
14 281058
15 294937
16 298146
17 292488
18 292496
19 295046