Skip to content

Faster sorting algo #999

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Jan 15, 2015
Merged

Faster sorting algo #999

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
2 changes: 2 additions & 0 deletions UPGRADING
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -56,6 +56,8 @@ PHP X.Y UPGRADE NOTES
output buffer is created in an output buffer handler.
. Added zend_memnstr_ex, which is based on string matching sunday algo.
. Added zend_memnrstr, zend_memnrstr_ex.
. Added hybrid sorting algo zend_sort for better performance.
. Added stable sorting algo zend_insert_sort.

- DBA
. dba_delete() now returns false if the key was not found for the inifile
Expand Down
2 changes: 1 addition & 1 deletion Zend/Makefile.am
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -13,7 +13,7 @@ libZend_la_SOURCES=\
zend_vm_opcodes.c zend_opcode.c zend_operators.c zend_ptr_stack.c zend_stack.c \
zend_variables.c zend.c zend_API.c zend_extensions.c zend_hash.c \
zend_list.c zend_indent.c zend_builtin_functions.c zend_sprintf.c \
zend_ini.c zend_qsort.c zend_objects.c zend_object_handlers.c \
zend_ini.c zend_sort.c zend_objects.c zend_object_handlers.c \
zend_objects_API.c zend_ts_hash.c zend_stream.c \
zend_default_classes.c \
zend_iterators.c zend_interfaces.c zend_exceptions.c \
Expand Down
13 changes: 4 additions & 9 deletions Zend/tests/methods-on-non-objects-usort.phpt
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -23,21 +23,16 @@ int(4096)
string(43) "Call to a member function compare() on null"
int(4096)
string(43) "Call to a member function compare() on null"
int(4096)
string(43) "Call to a member function compare() on null"
int(4096)
string(43) "Call to a member function compare() on null"
array(5) {
[0]=>
int(-1)
int(1)
[1]=>
int(3)
int(4)
[2]=>
int(2)
[3]=>
int(4)
int(3)
[4]=>
int(1)
int(-1)
}
Alive

4 changes: 2 additions & 2 deletions Zend/zend_API.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1715,7 +1715,7 @@ static int zend_startup_module_zval(zval *zv) /* {{{ */
}
/* }}} */

static void zend_sort_modules(void *base, size_t count, size_t siz, compare_func_t compare) /* {{{ */
static void zend_sort_modules(void *base, size_t count, size_t siz, compare_func_t compare, swap_func_t swp) /* {{{ */
{
Bucket *b1 = base;
Bucket *b2;
Expand Down Expand Up @@ -1821,7 +1821,7 @@ ZEND_API void zend_collect_module_handlers(void) /* {{{ */

ZEND_API int zend_startup_modules(void) /* {{{ */
{
zend_hash_sort(&module_registry, zend_sort_modules, NULL, 0);
zend_hash_sort_ex(&module_registry, zend_sort_modules, NULL, 0);
zend_hash_apply(&module_registry, zend_startup_module_zval);
return SUCCESS;
}
Expand Down
47 changes: 44 additions & 3 deletions Zend/zend_hash.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1663,8 +1663,47 @@ ZEND_API zval *zend_hash_get_current_data_ex(HashTable *ht, HashPosition *pos)
}
}

ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func,
compare_func_t compar, zend_bool renumber)
ZEND_API void zend_hash_bucket_swap(Bucket *p, Bucket *q) {
zval val;
zend_ulong h;
zend_string *key;

ZVAL_COPY_VALUE(&val, &p->val);
h = p->h;
key = p->key;

ZVAL_COPY_VALUE(&p->val, &q->val);
p->h = q->h;
p->key = q->key;

ZVAL_COPY_VALUE(&q->val, &val);
q->h = h;
q->key = key;
}

ZEND_API void zend_hash_bucket_renum_swap(Bucket *p, Bucket *q) {
zval val;

ZVAL_COPY_VALUE(&val, &p->val);
ZVAL_COPY_VALUE(&p->val, &q->val);
ZVAL_COPY_VALUE(&q->val, &val);
}

ZEND_API void zend_hash_bucket_packed_swap(Bucket *p, Bucket *q) {
zval val;
zend_ulong h;

ZVAL_COPY_VALUE(&val, &p->val);
h = p->h;

ZVAL_COPY_VALUE(&p->val, &q->val);
p->h = q->h;

ZVAL_COPY_VALUE(&q->val, &val);
q->h = h;
}

ZEND_API int zend_hash_sort_ex(HashTable *ht, sort_func_t sort, compare_func_t compar, zend_bool renumber)
{
Bucket *p;
uint32_t i, j;
Expand All @@ -1688,7 +1727,9 @@ ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func,
}
}

(*sort_func)((void *) ht->arData, i, sizeof(Bucket), compar);
sort((void *)ht->arData, i, sizeof(Bucket), compar,
(swap_func_t)(renumber? zend_hash_bucket_renum_swap :
((ht->u.flags & HASH_FLAG_PACKED) ? zend_hash_bucket_packed_swap : zend_hash_bucket_swap)));

HANDLE_BLOCK_INTERRUPTIONS();
ht->nNumUsed = i;
Expand Down
8 changes: 7 additions & 1 deletion Zend/zend_hash.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -201,13 +201,19 @@ typedef struct _HashPointer {
ZEND_API void zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor);
ZEND_API void _zend_hash_merge(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, zend_bool overwrite ZEND_FILE_LINE_DC);
ZEND_API void zend_hash_merge_ex(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, merge_checker_func_t pMergeSource, void *pParam);
ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func, compare_func_t compare_func, zend_bool renumber);
ZEND_API void zend_hash_bucket_swap(Bucket *p, Bucket *q);
ZEND_API void zend_hash_bucket_renum_swap(Bucket *p, Bucket *q);
ZEND_API void zend_hash_bucket_packed_swap(Bucket *p, Bucket *q);
ZEND_API int zend_hash_sort_ex(HashTable *ht, sort_func_t sort_func, compare_func_t compare_func, zend_bool renumber);
ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered);
ZEND_API zval *zend_hash_minmax(const HashTable *ht, compare_func_t compar, uint32_t flag);

#define zend_hash_merge(target, source, pCopyConstructor, overwrite) \
_zend_hash_merge(target, source, pCopyConstructor, overwrite ZEND_FILE_LINE_CC)

#define zend_hash_sort(ht, compare_func, renumber) \
zend_hash_sort_ex(ht, zend_sort, compare_func, renumber)

#define zend_hash_num_elements(ht) \
(ht)->nNumOfElements

Expand Down
4 changes: 2 additions & 2 deletions Zend/zend_ini.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -19,7 +19,7 @@
/* $Id$ */

#include "zend.h"
#include "zend_qsort.h"
#include "zend_sort.h"
#include "zend_API.h"
#include "zend_ini.h"
#include "zend_alloc.h"
Expand Down Expand Up @@ -202,7 +202,7 @@ static int ini_key_compare(const void *a, const void *b) /* {{{ */

ZEND_API void zend_ini_sort_entries(void) /* {{{ */
{
zend_hash_sort(EG(ini_directives), zend_qsort, ini_key_compare, 0);
zend_hash_sort(EG(ini_directives), ini_key_compare, 0);
}
/* }}} */

Expand Down
14 changes: 11 additions & 3 deletions Zend/zend_llist.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -21,7 +21,7 @@

#include "zend.h"
#include "zend_llist.h"
#include "zend_qsort.h"
#include "zend_sort.h"

ZEND_API void zend_llist_init(zend_llist *l, size_t size, llist_dtor_func_t dtor, unsigned char persistent)
{
Expand All @@ -33,7 +33,6 @@ ZEND_API void zend_llist_init(zend_llist *l, size_t size, llist_dtor_func_t dtor
l->persistent = persistent;
}


ZEND_API void zend_llist_add_element(zend_llist *l, void *element)
{
zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
Expand Down Expand Up @@ -186,6 +185,14 @@ ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func)
}
}

static void zend_llist_swap(zend_llist_element **p, zend_llist_element **q)
{
zend_llist_element *t;
t = *p;
*p = *q;
*q = t;
}

ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func)
{
size_t i;
Expand All @@ -205,7 +212,8 @@ ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func)
*ptr++ = element;
}

zend_qsort(elements, l->count, sizeof(zend_llist_element *), (compare_func_t) comp_func);
zend_sort(elements, l->count, sizeof(zend_llist_element *),
(compare_func_t) comp_func, (swap_func_t) zend_llist_swap);

l->head = elements[0];
elements[0]->prev = NULL;
Expand Down
133 changes: 0 additions & 133 deletions Zend/zend_qsort.c
View file
Open in desktop

This file was deleted.

Loading