MonetDB: default - Reduce cost of sorting lists by removing a qu...

[Sjoerd Mullender]

Changeset: d8009b77c0f9 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=d8009b77c0f9
Modified Files:
        sql/common/sql_list.c
        sql/server/rel_optimizer.c
Branch: default
Log Message:

Reduce cost of sorting lists by removing a quadratic part.


diffs (150 lines):

diff --git a/sql/common/sql_list.c b/sql/common/sql_list.c
--- a/sql/common/sql_list.c
+++ b/sql/common/sql_list.c
@@ -473,28 +473,27 @@ list_keysort(list *l, int *keys, fdup du
 {
        list *res;
        node *n = NULL;
-       int i, j, *pos, cnt = list_length(l);
+       int i, cnt = list_length(l);
+       void **data;
 
-       pos = (int*)GDKmalloc(cnt*sizeof(int));
-       if (pos == NULL) {
+       data = GDKmalloc(cnt*sizeof(void *));
+       if (data == NULL) {
                return NULL;
        }
        res = list_new_(l);
        if (res == NULL) {
-               GDKfree(pos);
+               GDKfree(data);
                return NULL;
        }
        for (n = l->h, i = 0; n; n = n->next, i++) {
-               pos[i] = i;
+               data[i] = n->data;
        }
        /* sort descending */
-       GDKqsort_rev(keys, pos, NULL, cnt, sizeof(int), sizeof(int), TYPE_int);
-       for(j=0; j<cnt; j++) {
-               for(n = l->h, i = 0; i != pos[j]; n = n->next, i++) 
-                       assert(n);
-               list_append(res, dup?dup(n->data):n->data);
+       GDKqsort_rev(keys, data, NULL, cnt, sizeof(int), sizeof(void *), 
TYPE_int);
+       for(i=0; i<cnt; i++) {
+               list_append(res, dup?dup(data[i]):data[i]);
        }
-       GDKfree(pos);
+       GDKfree(data);
        return res;
 }
 
@@ -503,36 +502,33 @@ list_sort(list *l, fkeyvalue key, fdup d
 {
        list *res;
        node *n = NULL;
-       int i, j, *keys, *pos, cnt = list_length(l);
+       int i, *keys, cnt = list_length(l);
+       void **data;
 
-       keys = (int*)GDKmalloc(cnt*sizeof(int));
-       pos = (int*)GDKmalloc(cnt*sizeof(int));
-       if (keys == NULL || pos == NULL) {
-               if (keys)
-                       GDKfree(keys);
-               if (pos)
-                       GDKfree(pos);
+       keys = GDKmalloc(cnt*sizeof(int));
+       data = GDKmalloc(cnt*sizeof(void *));
+       if (keys == NULL || data == NULL) {
+               GDKfree(keys);
+               GDKfree(data);
                return NULL;
        }
        res = list_new_(l);
        if (res == NULL) {
                GDKfree(keys);
-               GDKfree(pos);
+               GDKfree(data);
                return NULL;
        }
        for (n = l->h, i = 0; n; n = n->next, i++) {
                keys[i] = key(n->data);
-               pos[i] = i;
+               data[i] = n->data;
        }
        /* sort descending */
-       GDKqsort_rev(keys, pos, NULL, cnt, sizeof(int), sizeof(int), TYPE_int);
-       for(j=0; j<cnt; j++) {
-               for(n = l->h, i = 0; i != pos[j]; n = n->next, i++) 
-                       assert(n);
-               list_append(res, dup?dup(n->data):n->data);
+       GDKqsort_rev(keys, data, NULL, cnt, sizeof(int), sizeof(void *), 
TYPE_int);
+       for(i=0; i<cnt; i++) {
+               list_append(res, dup?dup(data[i]):data[i]);
        }
        GDKfree(keys);
-       GDKfree(pos);
+       GDKfree(data);
        return res;
 }
 
diff --git a/sql/server/rel_optimizer.c b/sql/server/rel_optimizer.c
--- a/sql/server/rel_optimizer.c
+++ b/sql/server/rel_optimizer.c
@@ -622,22 +622,23 @@ order_join_expressions(mvc *sql, list *d
 {
        list *res;
        node *n = NULL;
-       int i, j, *keys, *pos, cnt = list_length(dje);
+       int i, *keys, cnt = list_length(dje);
+       void **data;
        int debug = mvc_debug_on(sql, 16);
 
-       keys = (int*)malloc(cnt*sizeof(int));
-       pos = (int*)malloc(cnt*sizeof(int));
-       if (keys == NULL || pos == NULL) {
+       keys = malloc(cnt*sizeof(int));
+       data = malloc(cnt*sizeof(void *));
+       if (keys == NULL || data == NULL) {
                if (keys)
                        free(keys);
-               if (pos)
-                       free(pos);
+               if (data)
+                       free(data);
                return NULL;
        }
        res = sa_list(sql->sa);
        if (res == NULL) {
                free(keys);
-               free(pos);
+               free(data);
                return NULL;
        }
        for (n = dje->h, i = 0; n; n = n->next, i++) {
@@ -654,18 +655,15 @@ order_join_expressions(mvc *sql, list *d
                        if (r && is_select(r->op) && r->exps)
                                keys[i] += list_length(r->exps)*10 + 
exps_count(r->exps)*debug;
                }
-               pos[i] = i;
+               data[i] = n->data;
        }
        /* sort descending */
-       if (cnt > 1) 
-               GDKqsort_rev(keys, pos, NULL, cnt, sizeof(int), sizeof(int), 
TYPE_int);
-       for(j=0; j<cnt; j++) {
-               for(n = dje->h, i = 0; i != pos[j]; n = n->next, i++) 
-                       ;
-               list_append(res, n->data);
+       GDKqsort_rev(keys, data, NULL, cnt, sizeof(int), sizeof(void *), 
TYPE_int);
+       for(i=0; i<cnt; i++) {
+               list_append(res, data[i]);
        }
        free(keys);
-       free(pos);
+       free(data);
        return res;
 }
 
_______________________________________________
checkin-list mailing list
checkin-list@monetdb.org
https://www.monetdb.org/mailman/listinfo/checkin-list