[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [56618] trunk/blender/source/blender: bmesh: optimize bmesh_vert_separate, redice allocs ( best cast it wont do any allocs).

[Campbell Barton]

Revision: 56618
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=56618
Author:   campbellbarton
Date:     2013-05-09 12:46:35 +0000 (Thu, 09 May 2013)
Log Message:
-----------
bmesh: optimize bmesh_vert_separate, redice allocs (best cast it wont do any allocs).
gives approx 16% overall speedup to edgesplit modifier.

also reduce size of smallhash stack, was 521, which got doubled and was quite large on the stack. reduce to 64.

Modified Paths:
--------------
    trunk/blender/source/blender/blenlib/BLI_smallhash.h
    trunk/blender/source/blender/bmesh/intern/bmesh_core.c

Modified: trunk/blender/source/blender/blenlib/BLI_smallhash.h
===================================================================
--- trunk/blender/source/blender/blenlib/BLI_smallhash.h	2013-05-09 11:43:48 UTC (rev 56617)
+++ trunk/blender/source/blender/blenlib/BLI_smallhash.h	2013-05-09 12:46:35 UTC (rev 56618)
@@ -43,7 +43,7 @@
 } SmallHashEntry;
 
 /*how much stack space to use before dynamically allocating memory*/
-#define SMSTACKSIZE 521
+#define SMSTACKSIZE 64
 typedef struct SmallHash {
 	SmallHashEntry *table;
 	SmallHashEntry _stacktable[SMSTACKSIZE];

Modified: trunk/blender/source/blender/bmesh/intern/bmesh_core.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_core.c	2013-05-09 11:43:48 UTC (rev 56617)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_core.c	2013-05-09 12:46:35 UTC (rev 56618)
@@ -30,6 +30,7 @@
 #include "BLI_math_vector.h"
 #include "BLI_listbase.h"
 #include "BLI_array.h"
+#include "BLI_smallhash.h"
 
 #include "BLF_translation.h"
 
@@ -1890,45 +1891,62 @@
  */
 bool bmesh_vert_separate(BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len)
 {
-	BMEdge **stack = NULL;
-	BLI_array_staticdeclare(stack, BM_DEFAULT_ITER_STACK_SIZE);
+	const int v_edgetot = BM_vert_face_count(v);
+	BMEdge **stack = BLI_array_alloca(stack, v_edgetot);
+	unsigned int _stack_i;
+
+	/* */
+#define STACK_INIT(stack)     ((void)stack, (void)(_stack_i = 0))
+#define STACK_PUSH(stack, val)  (void)((stack)[_stack_i++] = val)
+#define STACK_POP(stack)       ((void)0, (_stack_i ? ((stack)[--_stack_i]) : NULL))
+#define STACK_FREE(stack)      ((void)stack)
+
+	SmallHash visithash;
 	BMVert **verts = NULL;
-	GHash *visithash;
 	BMIter eiter, liter;
 	BMLoop *l;
 	BMEdge *e;
 	int i, maxindex;
 	BMLoop *l_new;
 
-	visithash = BLI_ghash_ptr_new(__func__);
+	BLI_smallhash_init(&visithash);
 
+	STACK_INIT(stack);
+
 	maxindex = 0;
 	BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
-		if (BLI_ghash_haskey(visithash, e)) {
+		if (BLI_smallhash_haskey(&visithash, (uintptr_t)e)) {
 			continue;
 		}
 
-		/* Prime the stack with this unvisited edge */
-		BLI_array_append(stack, e);
-
 		/* Considering only edges and faces incident on vertex v, walk
 		 * the edges & faces and assign an index to each connected set */
-		while ((e = BLI_array_pop(stack))) {
-			BLI_ghash_insert(visithash, e, SET_INT_IN_POINTER(maxindex));
+		do {
+			BLI_smallhash_insert(&visithash, (uintptr_t)e, SET_INT_IN_POINTER(maxindex));
 
-			BM_ITER_ELEM (l, &liter, e, BM_LOOPS_OF_EDGE) {
-				l_new = (l->v == v) ? l->prev : l->next;
-				if (!BLI_ghash_haskey(visithash, l_new->e)) {
-					BLI_array_append(stack, l_new->e);
-				}
+			if (e->l) {
+				BMLoop *l_iter, *l_first;
+				l_iter = l_first = e->l;
+				do {
+					l_new = (l_iter->v == v) ? l_iter->prev : l_iter->next;
+					if (!BLI_smallhash_haskey(&visithash, (uintptr_t)l_new->e)) {
+						STACK_PUSH(stack, l_new->e);
+					}
+				} while ((l_iter = l_iter->radial_next) != l_first);
 			}
-		}
+		} while ((e = STACK_POP(stack)));
 
 		maxindex++;
 	}
 
 	/* Make enough verts to split v for each group */
-	verts = MEM_callocN(sizeof(BMVert *) * maxindex, __func__);
+	if (r_vout != NULL) {
+		verts = MEM_callocN(sizeof(BMVert *) * maxindex, __func__);
+	}
+	else {
+		verts = BLI_array_alloca(verts, maxindex);
+	}
+
 	verts[0] = v;
 	for (i = 1; i < maxindex; i++) {
 		verts[i] = BM_vert_create(bm, v->co, v, 0);
@@ -1961,23 +1979,23 @@
 	 * by modifying data it loops over [#30632], this re-uses the 'stack' variable which is a bit
 	 * bad practice but save alloc'ing a new array - note, the comment above is useful, keep it
 	 * if you are tidying up code - campbell */
-	BLI_array_empty(stack);
+	STACK_INIT(stack);
 	BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
 		if (l->v == v) {
-			BLI_array_append(stack, (BMEdge *)l);
+			STACK_PUSH(stack, (BMEdge *)l);
 		}
 	}
-	while ((l = (BMLoop *)(BLI_array_pop(stack)))) {
-		if ((i = GET_INT_FROM_POINTER(BLI_ghash_lookup(visithash, l->e)))) {
+	while ((l = (BMLoop *)(STACK_POP(stack)))) {
+		if ((i = GET_INT_FROM_POINTER(BLI_smallhash_lookup(&visithash, (uintptr_t)l->e)))) {
 			l->v = verts[i];
 		}
 	}
 #endif
 
-	BLI_array_free(stack);
+	STACK_FREE(stack);
 
 	BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
-		i = GET_INT_FROM_POINTER(BLI_ghash_lookup(visithash, e));
+		i = GET_INT_FROM_POINTER(BLI_smallhash_lookup(&visithash, (uintptr_t)e));
 		if (i == 0) {
 			continue;
 		}
@@ -1988,7 +2006,7 @@
 		bmesh_disk_edge_append(e, verts[i]);
 	}
 
-	BLI_ghash_free(visithash, NULL, NULL);
+	BLI_smallhash_release(&visithash);
 
 	for (i = 0; i < maxindex; i++) {
 		BM_CHECK_ELEMENT(verts[i]);
@@ -2001,10 +2019,12 @@
 	if (r_vout != NULL) {
 		*r_vout = verts;
 	}
-	else {
-		MEM_freeN(verts);
-	}
 
+#undef STACK_INIT
+#undef STACK_PUSH
+#undef STACK_POP
+#undef STACK_FREE
+
 	return true;
 }