robin hood hashing

https://github.com/Tessil/robin-map

std::map과 std::unordered_map 을 속도면에서 발라버리는.. 헤쉬맵..
사용법은 std와 동일하다..

단순히 std::map과 std::unordered_map 을 tsl::robin_map 으로 바꾸어서 컴파일하니..
노드 1488581 개를 가진 메시를 기준으로..
메시 구조를 빌딩하는 타임이 26초 걸리던것이.. 18초가 되었다.. 지쟈스..

clear도 빨라졌네.. ㅎㅎ

여러 해쉬 라이브러리와 비교한 밴치마킹 사이트..
https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-03-01-result-InsertHugeInt/

libglu 테스트

libglu 라이브러리중 linked list인 ls** 함수들과 hash table인 st_** 함수들을 조합하면 STL의 vector 클래스를 흉내낼 수 있다.
사내 프로젝트에서도 자주 이용하는 편이다.
아래는 mingw로 간단하게 테스트해본 코드이다.

#include <string.h>

#include <util.h>
#include <list.h>
#include <st.h>

typedef struct _child_list {
    int element;
} *child_list;

typedef struct _db {
	char *name;
    int age;
    lsList *child_list;		// linked list
} *db;

st_table *mydb_table;		// hash table

st_strcasehash(string, modulus)
register char *string;
int modulus;
{
    register int val = 0;
    register int c;
    register int c2;
    
    while ((c = *string++) != '\0') {
	if ( c >= 'a' && c <= 'z' ) {
	    // capitaliize c
	    c2 = c - ( 'a' - 'A' );
	} else {
	    c2 = c;
	}
	val = val*997 + c2;
    }

    return ((val < 0) ? -val : val)%modulus;
}

int main(void)
{
	char *name;
	db mydb;
    st_generator *gen;
    char *idx;
    char *key;
	
    mydb_table = st_init_table(strcmp, st_strcasehash);

	// append data
	{
		mydb = malloc(sizeof(struct _db));

		mydb->age = 10;
		name = malloc(sizeof(char)*(strlen("name1")+1));
		sprintf(name, "name1");
		mydb->name = strdup(name);

		mydb->child_list = lsCreate();
		lsNewEnd(mydb->child_list, 1, LS_NH);
		lsNewEnd(mydb->child_list, 2, LS_NH);
		lsNewEnd(mydb->child_list, 3, LS_NH);
		lsNewEnd(mydb->child_list, 4, LS_NH);

		st_insert(mydb_table, strdup(name), (db)mydb);
	}

	
	// append data
	{
		mydb = malloc(sizeof(struct _db));
		mydb->age = 10;
		name = malloc(sizeof(char)*(strlen("name2")+1));
		sprintf(name, "name2");
		mydb->name = strdup(name);

		mydb->child_list = lsCreate();
		lsNewEnd(mydb->child_list, 5, LS_NH);
		lsNewEnd(mydb->child_list, 6, LS_NH);
		lsNewEnd(mydb->child_list, 7, LS_NH);
		lsNewEnd(mydb->child_list, 8, LS_NH);

		st_insert(mydb_table, strdup(name), (db)mydb);
	}

	// display datas
    st_foreach_item(mydb_table, gen, &idx, &mydb) {
		lsGen gen2;
		int data;

		fprintf(stdout, "----> %s\n", mydb->name);

		lsForEachItem(mydb->child_list, gen2, data) {
			fprintf(stdout, "%d ", data);
		}
		fprintf(stdout, "\n");
		fflush(stdout);
	}

	return 0;
}
$ gcc -o test.exe test.c -lglu
$ ./test
----> name2
5 6 7 8 
----> name1
1 2 3 4