gnumeric r17094 - in trunk: . src

[mortenw svn gnome org]

Author: mortenw
Date: Mon Jan 26 02:00:40 2009
New Revision: 17094
URL: http://svn.gnome.org/viewvc/gnumeric?rev=17094&view=rev

Log:
2009-01-25  Morten Welinder  <terra gnome org>

	* src/dependent.c (link_range_dep, unlink_range_dep): Restrict the
	range that goes into the bucket to the intersection of the source
	range and the bucket area.  This improves dependency search
	efficiency markedly when a large number of large ranges are in
	play.  Fixes performance part of #567389.



Modified:
   trunk/ChangeLog
   trunk/NEWS
   trunk/src/dependent.c

Modified: trunk/NEWS
==============================================================================
--- trunk/NEWS	(original)
+++ trunk/NEWS	Mon Jan 26 02:00:40 2009
@@ -25,7 +25,8 @@
 	* Fix crash when exporting an empty contour plot to .xls.  [#557027]
 	* Add widgets in the graph guru first page to allow finer selection
 	of data.
-	* Fix labels length for charts generated by the histogram tool. [#552721]
+	* Fix labels length for charts generated by the histogram tool.
+	[#552721]
 	* Fix loss od new graphs when clicking on an existing sheet
 	object. [#151789]
 	* Do not export invalid AXESUSED data to .xls. [#567783]
@@ -78,6 +79,8 @@
 	* Fix crash and criticals in dbf import.  [#568454]
 	* Fix colour problem in LaTeX export.  [#568860]
 	* Fix loop while loading lotus file.  [#568917]
+	* Fix performance problem in dependency tracking given large
+	number of large ranges.  [#567389]
 
 --------------------------------------------------------------------------
 Gnumeric 1.9.3

Modified: trunk/src/dependent.c
==============================================================================
--- trunk/src/dependent.c	(original)
+++ trunk/src/dependent.c	Mon Jan 26 02:00:40 2009
@@ -900,17 +900,21 @@
 {
 	int i = BUCKET_OF_ROW (r->range.start.row);
 	int const end = BUCKET_OF_ROW (r->range.end.row);
+	DependencyRange r2 = *r;
 
 	for ( ; i <= end; i++) {
-		/* Look it up */
 		DependencyRange *result;
 
+		/* Restrict range to bucket.  */
+		r2.range.start.row = MAX (r->range.start.row, BUCKET_START_ROW (i));
+		r2.range.end.row = MIN (r->range.end.row, BUCKET_END_ROW (i));
+
 		if (deps->range_hash[i] == NULL)
 			deps->range_hash[i] = g_hash_table_new (
 				(GHashFunc)  deprange_hash,
 				(GEqualFunc) deprange_equal);
 		else {
-			result = g_hash_table_lookup (deps->range_hash[i], r);
+			result = g_hash_table_lookup (deps->range_hash[i], &r2);
 			if (result) {
 				/* Inserts if it is not already there */
 				micro_hash_insert (&result->deps, dep);
@@ -920,7 +924,7 @@
 
 		/* Create a new DependencyRange structure */
 		result = go_mem_chunk_alloc (deps->range_pool);
-		*result = *r;
+		*result = r2;
 		micro_hash_init (&result->deps, dep);
 		g_hash_table_insert (deps->range_hash[i], result, result);
 	}
@@ -932,13 +936,19 @@
 {
 	int i = BUCKET_OF_ROW (r->range.start.row);
 	int const end = BUCKET_OF_ROW (r->range.end.row);
+	DependencyRange r2 = *r;
 
 	if (!deps)
 		return;
 
 	for ( ; i <= end; i++) {
-		DependencyRange *result =
-			g_hash_table_lookup (deps->range_hash[i], r);
+		DependencyRange *result;
+
+		/* Restrict range to bucket.  */
+		r2.range.start.row = MAX (r->range.start.row, BUCKET_START_ROW (i));
+		r2.range.end.row = MIN (r->range.end.row, BUCKET_END_ROW (i));
+
+		result = g_hash_table_lookup (deps->range_hash[i], &r2);
 		if (result) {
 			micro_hash_remove (&result->deps, dep);
 			if (micro_hash_is_empty (&result->deps)) {