C skiplist implementation is unexpectedly linear

Question

I've been using a skiplist my library provides in some of my programs, and recently noticed it's slower than expected. Upon closer examination with this test program:

#include "usflib2.h"
#include <stdio.h>
#include <time.h>

uint64_t test(uint64_t);

int main() {
    uint64_t i, j, avg = 0;

    srand(time(NULL));
    printf("WARN: The skiplist must be made to return number of steps on access for this test to work.\n");

    for (i = 2; i < 10000000; i *= 2) {
        for (j = 0; j < 100; j++) {
            avg += test(i);
        }   

        printf("(%lu, %lu)\n", i, avg/100);
        fflush(stdout);
    }   
    return 0;
}

uint64_t test(uint64_t cycles) {
    uint64_t i;

    usf_skiplist *skp;
    skp = usf_skset(NULL, 0, USFNULL);

    for (i = 0; i < cycles; i++) {
        usf_skset(skp, i, USFDATAU(i));
    }   

    i = usf_skget(skp, i/2).u;

    /* Cleanup */
    usf_freesk(skp);

    return i;
}

The results always point to a linear time growth when accessing the middle element :

I've re-looked a few times, but cannot find what is wrong. Perhaps it is my understanding of the skiplist that is flawed ? Nevertheless, here are implementations for both usf_skset() and usf_skget()

usf_skiplist *usf_skset(usf_skiplist *skiplist, uint64_t i, usf_data data) {
    int j;
    usf_skipnode *node, *next, **ptrs;
    usf_skipnode *position[USF_SKIPLIST_HEADSIZE];

    if (skiplist == NULL) { //Make skiplist
        //Allocate skiplist
        skiplist = malloc(sizeof(usf_skiplist));
        skiplist -> size = 1; //Base node

        node = malloc(sizeof(usf_skipnode)); //Head

        //Allocate head pointers
        node -> nextnodes = calloc(sizeof(usf_skipnode **), USF_SKIPLIST_HEADSIZE);

        //Set base data
        node -> index = 0;
        node -> data = USFNULL;

        skiplist -> head = node;
    }

    //Insert data at index i in skiplist
    node = skiplist -> head; //Start

    for (j = USF_SKIPLIST_HEADSIZE - 1; j >= 0; j--) {
        next = node -> nextnodes[j];

        while (next && next -> index <= i) {
            node = next;
            next = node -> nextnodes[j];
        }

        //At max node in this stage
        position[j] = node;
    }

    if (node -> index == i) {
        //Already present
        node -> data = data;
        return skiplist;
    }

    //Add and link
    node = malloc(sizeof(usf_skipnode));
    node -> index = i;
    node -> data = data;

    for (j = 1; j < USF_SKIPLIST_HEADSIZE; j++)
        if (rand() & 1) break; //Probabilistic upkeep

    ptrs = malloc(sizeof(usf_skipnode *) * j);

    for (j--; j >= 0; j--) {
        ptrs[j] = position[j] -> nextnodes[j]; //Link to next
        position[j] -> nextnodes[j] = node; //Link prev to this
    }

    node -> nextnodes = ptrs;
    skiplist -> size++; //Add element
    return skiplist;
}

Note that here I've modified the get function to return the number of stations (or steps) taken to reach the destination.

usf_data usf_skget(usf_skiplist *skiplist, uint64_t i) {
    uint64_t TEMP = 0; /* TEMPORARY */

    int j;
    usf_skipnode *node, *next;

    node = skiplist -> head;

    for (j = USF_SKIPLIST_HEADSIZE - 1; j >= 0; j--) {
        next = node -> nextnodes[j];

        while (next && next -> index <= i) {
            TEMP++; /* TEMPORARY */

            /* Loop unrolling: two iterations per while cycle */
            node = next;
            if ((next = node -> nextnodes[j]) == NULL || next -> index > i) break;

            node = next;
            next = node -> nextnodes[j];
        }

        if (node -> index == i) break;
    }

    return USFDATAU(TEMP); /*TEMPORARY*/
    if (node -> index != i) return USFNULL;

    return node -> data;
}

And the usfskiplist.h header:

#ifndef USFSKIPLIST_H
#define USFSKIPLIST_H

#include <stdlib.h>
#include "usfdata.h"

#define USF_SKIPLIST_HEADSIZE 24

typedef struct usf_skipnode {
    struct usf_skipnode **nextnodes;
    usf_data data;
    uint64_t index;
} usf_skipnode;

typedef struct usf_skiplist {
    usf_skipnode *head;
    uint64_t size;
} usf_skiplist;

usf_skiplist *usf_skset(usf_skiplist *, uint64_t, usf_data);
usf_data usf_skget(usf_skiplist *, uint64_t);
usf_data usf_skdel(usf_skiplist *, uint64_t);
void usf_freesk(usf_skiplist *); 

#endif

Answer 1

Okay, so after Ilya Bursov's comment I have realized I had forgotten to reset the avg after each test... It actually was logarithmic all along.

I think the program which "tipped me off" just did so many skip list accesses it led me to believe the skip list was at fault for the speed.