Programming

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <sys/types.h>
#include <stdint.h>

#define MEMBERS	(1024L*1024L)	// ONE MEEEEEELION D^GMEMBERS

struct node
{
	int sval;
	struct node *prev, *next;
	char waste[64];
};

int compar(const struct node **a, const struct node **b)
{	return((*b)->sval - (*a)->sval);	}


/* returns a timestamp in microseconds */
int64_t micro(void)
{
	int64_t val;
	struct timeval tv;
	gettimeofday(&tv, NULL);
	val=tv.tv_sec;
	val*=1000000;
	val+=tv.tv_usec;
	return(val);
}

int main(void)
{
	unsigned long l;
	int64_t begin,end1,end2;

	struct node *mem=malloc(sizeof(struct node)*MEMBERS);
	struct node **pmem=malloc(sizeof(void *)*MEMBERS);

/*	fprintf(stderr, "%ld K structures at %p\n",
		(sizeof(struct node)*MEMBERS)>>10, mem);*/

/*	fprintf(stderr, "%ld K pointers at %p\n",
		(sizeof(void *)*MEMBERS)>>10, pmem);*/

	for(l=0; l<MEMBERS; l++)
	{
		mem[l].sval=rand() + (rand()*RAND_MAX);
		if(mem[l].sval < 0) mem[l].sval = (-mem[l].sval)-1;
		pmem[l]=mem+l;
	}

	begin=micro();
	qsort(pmem, MEMBERS, sizeof(void *), compar);
	end1=micro();

	pmem[0]->prev=NULL;
	pmem[0]->next=pmem[1];
	pmem[MEMBERS-1]->next=NULL;
	pmem[MEMBERS-1]->prev=pmem[MEMBERS-2];

	for(l=1; l<(MEMBERS-1); l++)
	{
		pmem[l]->prev=pmem[l-1];
		pmem[l]->next=pmem[l+1];
	}

	{
		struct node *newhead=pmem[0];
		while(newhead != NULL)
		{
//			printf("%u\n", newhead->sval);
			newhead=newhead->next;
		}
	}
	end2=micro();

	fprintf(stderr, " %d ms to sort\t",
		(int)((end1-begin)/(int64_t)1000L));
	fprintf(stderr, "+%d ms update\t", 
		(int)((end2-end1)/(int64_t)1000L));
	fprintf(stderr, "=%d ms\n",
		(int)((end2-begin)/(int64_t)1000L));

	free(mem);
	free(pmem);
}

$ cat /proc/cpuinfo
...
processor	: 1
vendor_id	: AuthenticAMD
cpu family	: 17
model		: 3
model name	: AMD Turion(tm) X2 Ultra Dual-Core Mobile ZM-82
stepping	: 1
cpu MHz		: 2200.000
cache size	: 1024 KB
physical id	: 0
siblings	: 2
core id		: 1
cpu cores	: 2
apicid		: 1
initial apicid	: 1
fpu		: yes
fpu_exception	: yes
cpuid level	: 1
wp		: yes
flags		: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov \
        pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt rdtscp \
        lm 3dnowext 3dnow constant_tsc rep_good nonstop_tsc extd_apicid pni \
        cx16 lahf_lm cmp_legacy svm extapic cr8_legacy 3dnowprefetch osvw \
        skinit lbrv svm_lock nrip_save
bogomips	: 4398.68
TLB size	: 1024 4K pages
clflush size	: 64
cache_alignment	: 64
address sizes	: 40 bits physical, 48 bits virtual
power management: ts ttp tm stc 100mhzsteps hwpstate

$ for ((N=0; N<10; N++)) ; do ./a.out ; done
 1024 ms sort	+230 ms update	=1255 ms
 1027 ms sort	+229 ms update	=1256 ms
 1026 ms sort	+229 ms update	=1256 ms
 1027 ms sort	+229 ms update	=1256 ms
 1020 ms sort	+226 ms update	=1246 ms
 1001 ms sort	+222 ms update	=1224 ms
 994 ms sort	+222 ms update	=1216 ms
 992 ms sort	+222 ms update	=1214 ms
 1023 ms sort	+230 ms update	=1253 ms
 1026 ms sort	+229 ms update	=1255 ms

$

/* preform merge sort on the linked list */
struct linked_list *mergesort(struct linked_list *head) 
{
    struct linked_list *head_one;
    struct linked_list *head_two;

    if((head == NULL) || (head->next == NULL)) 
    return head;

    head_one = head;
    head_two = head->next;
    while((head_two != NULL) && (head_two->next != NULL)) 
    {
        head = head->next;
        head_two = head->next->next;
     }

    head_two = head->next;
    head->next = NULL;

    return merge(mergesort(head_one), mergesort(head_two));
}

/* merge the lists.. */
struct linked_list *merge(struct linked_list *head_one, struct linked_list *head_two) 
{
    struct linked_list *head_three;

    if(head_one == NULL) 
    return head_two;

    if(head_two == NULL)
    return head_one;

    if(head_one->cluster_number < head_two->cluster_number) 
    {
        head_three = head_one;
        head_three->next = merge(head_one->next, head_two);
     } 
    
    else
    
    {
        head_three = head_two;
        head_three->next = merge(head_one, head_two->next);
    }

    return head_three;
}

/* Merges two sorted lists together into one sorted list */
struct node *merge_list(struct node *l1, struct node *l2)
{
  struct node *cur=NULL;  /* Last node in list, where we work from */
  struct node *head=NULL; /* First node in list, our return value */

  /* If there's less than two lists, nothing to merge */
  if(l1==NULL)      return(l2);
  else if(l2==NULL) return(l1);

  while(l1||l2) /* Loop while either list is not empty */
  {
    struct node *tmp;
    if((!l1)||(!l2)) /* If one of the lists is empty */
    {
      /* cur is guaranteed to not be NULL.  This loop will have
         executed at least once by the time we reach here. */
      if(!l1) cur->next=l2; /* Append l2 to the end of the list */
      else    cur->next=l1; /* Append l1 to the end of the list */
      return(head); /* Return the new list */
    }
    else if(l1->sval < l2->sval) /* append first node from l2 */
    {
      if(head==NULL) /* empty list?  Don't append, just set */
      {
        head=cur=l2;
        l2=l2->next;
      }
      else /* append, go to next node */
      {
        cur->next=l2;
        cur=cur->next;
        l2=l2->next;
        cur->next=NULL;
      }
    }
    else /* append first node from l1 */
    {
      if(head==NULL) /* empty list?  don't append, just set */
      {
        head=cur=l1;
        l1=l1->next;
      }
      else /* append, go to next node */
      {
        cur->next=l1;
        cur=cur->next;
        l1=l1->next;
        cur->next=NULL;
      }
    }
  }
  return(head); /* Return the merged list */
}

/* Recursively sorts a linked list with the mergesort algorithm */
struct node *mergesort_list(struct node *list)
{
  /* pointers to first and last nodes of new lists */
  struct node *head[2],*tail[2];

  /* Empty list, return immediately */
  if(list==NULL)
    return(NULL);

  /* Set up list #0 */
  head[0]=tail[0]=list;
  list=list->next;

  /* Only one node, no sorting to be done */
  if(list==NULL)
    return(head[0]);

  /* Set up list #1 */
  head[1]=tail[1]=list;
  list=list->next;

  /* Loop through all the rest of the nodes in list, appending to and 
     splitting the nodes evenly between tail[0] and tail[1] */
  while(list!=NULL)
  {
    tail[0]->next=list;
    tail[0]=tail[0]->next;
    list=list->next;

    if(list!=NULL)
    {
      tail[1]->next=list;
      tail[1]=tail[1]->next;
      list=list->next;
    }    
  }

  /* Properly terminate the lists */
  tail[0]->next=NULL;
  tail[1]->next=NULL;

  /* recursively mergesort the two half-lists. */
  head[0]=mergesort_list(head[0]);
  head[1]=mergesort_list(head[1]);
  /* merge the now-sorted lists together, returning new head pointer. */
  return(merge_list(head[0],head[1]));
}