- added Imager's memory debugging code in an attempt to find the

   crash problem on Win32.  This seems to have eliminated the crash
   even when it's disabled (and just calls malloc/free/realloc)
   https://rt.cpan.org/Ticket/Display.html?id=18543
 - found the memory leak - we were creating an SV for the id to
   priority hash and nothing was releasing it
   https://rt.cpan.org/Ticket/Display.html?id=20018
 - the memory leak fix has become obsolete, we now avoid creating the
   SV at all by using the id in memory as a key to the hash.
 - added a verify method during debugging, it's not necessary anymore
   but someone else fiddling with the code might find it useful
 - pq_find_item() and pq_insertion_point() now use a binary search for
   larger queues.  These were the hotspots going by sprof profiling.

diff --git a/Array.xs b/Array.xs
index 0c2beb8f91f45ee059d6d4f2d4e0d6cff4c90283..338f8283d4cb3d4b3c889f959d013e60c4b30d9f 100644 (file)
--- a/Array.xs
+++ b/Array.xs
@@ -172,3 +172,7 @@ pq_peek_items(pq, filter, ...)
 void
 pq_dump(pq)
        POE::XS::Queue::Array pq
+
+void
+pq_verify(pq)
+       POE::XS::Queue::Array pq

diff --git a/alloc.h b/alloc.h
index 72e03d0bf3c21f73e5b3691f81c9ab5abf27858b..90aade8b1040adb289500057cc688b4d7fe4b11c 100644 (file)
--- a/alloc.h
+++ b/alloc.h
@@ -5,7 +5,7 @@
 #include <stddef.h>
 #include <stdlib.h>
 
-#define MEM_DEBUG
+/*#define MEM_DEBUG*/
 
 #ifdef MEM_DEBUG
 

diff --git a/queue.c b/queue.c
index 3bbc49c0c4eedebe91091e211994da0d47bdcf96..6468fcd71d9fd7c0ae7aa5f5fd637ff17117ca19 100644 (file)
--- a/queue.c
+++ b/queue.c
@@ -10,12 +10,22 @@
 #define DEBUG_ERR(x) x\r
 /*#define DEBUG_ERR(x)*/\r
 \r
+/*#define KEEP_STATS 1*/\r
+\r
+#if KEEP_STATS\r
+#define STATS(x) x\r
+#else\r
+#define STATS(x)\r
+#endif\r
+\r
 #define PQ_START_SIZE 10\r
 #define AT_START 0\r
 #define AT_END 1\r
 \r
 #define STUPID_IDS 0\r
 \r
+#define LARGE_QUEUE_SIZE 50\r
+\r
 /*\r
 We store the queue in a similar way to the way perl deals with arrays,\r
 we keep a block of memory, but the first element may or may not be in use,\r
@@ -55,6 +65,11 @@ struct poe_queue_tag {
 \r
   /* the actual entries */\r
   pq_entry *entries;\r
+\r
+#if KEEP_STATS\r
+  int total_finds;\r
+  int binary_finds;\r
+#endif\r
 };\r
 \r
 /*\r
@@ -79,6 +94,10 @@ pq_create(void) {
   if (pq->entries == NULL)\r
     croak("Out of memory");\r
 \r
+#if KEEP_STATS\r
+  pq->total_finds = pq->binary_finds = 0;\r
+#endif\r
+\r
   DEBUG( fprintf(stderr, "pq_create() => %p\n", pq) );\r
 \r
   return pq;\r
@@ -138,14 +157,12 @@ pq_new_id(poe_queue *pq, pq_priority_t priority) {
 \r
   return seq;\r
 #else\r
-  int seq = ++pq->queue_seq;;\r
-  SV *index = sv_2mortal(newSViv(seq));\r
+  pq_id_t seq = ++pq->queue_seq;;\r
 \r
-  while (hv_exists_ent(pq->ids, index, 0)) {\r
+  while (hv_exists(pq->ids, (char *)&seq, sizeof(seq))) {\r
     seq = ++pq->queue_seq;\r
-    sv_setiv(index, seq);\r
   }\r
-  hv_store_ent(pq->ids, index, newSVnv(priority), 0);\r
+  hv_store(pq->ids, (char *)&seq, sizeof(seq), newSVnv(priority), 0);\r
 #endif\r
 \r
   return seq;\r
@@ -159,9 +176,7 @@ void
 pq_release_id(poe_queue *pq, pq_id_t id) {\r
 #if STUPID_IDS\r
 #else\r
-  SV *id_sv = sv_2mortal(newSViv(id));\r
-\r
-  hv_delete_ent(pq->ids, id_sv, 0, 0);\r
+  hv_delete(pq->ids, (char *)&id, sizeof(id), 0);\r
 #endif\r
 }\r
 \r
@@ -183,12 +198,12 @@ pq_item_priority(poe_queue *pq, pq_id_t id, pq_priority_t *priority) {
 \r
   return 0;\r
 #else\r
-  HE *entry = hv_fetch_ent(pq->ids, sv_2mortal(newSViv(id)), 0, 0);\r
+  SV **entry = hv_fetch(pq->ids, (char *)&id, sizeof(id), 0);\r
 \r
-  if (!entry)\r
+  if (!entry || !*entry)\r
     return 0;\r
 \r
-  *priority = SvNV(HeVAL(entry));\r
+  *priority = SvNV(*entry);\r
 \r
   return 1;\r
 #endif\r
@@ -203,12 +218,12 @@ pq_set_id_priority(poe_queue *pq, pq_id_t id, pq_priority_t new_priority) {
 #if STUPID_IDS\r
   /* nothing to do, caller set it in the array */\r
 #else\r
-  HE *entry = hv_fetch_ent(pq->ids, sv_2mortal(newSViv(id)), 0, 0);\r
+  SV **entry = hv_fetch(pq->ids, (char *)&id, sizeof(id), 0);\r
 \r
-  if (!entry)\r
+  if (!entry && !*entry)\r
     croak("pq_set_priority: id not found");\r
 \r
-  sv_setnv(HeVAL(entry), new_priority);\r
+  sv_setnv(*entry, new_priority);\r
 #endif\r
 }\r
 \r
@@ -316,15 +331,38 @@ Internal.
 static\r
 int\r
 pq_insertion_point(poe_queue *pq, pq_priority_t priority) {\r
-  /* for now this is just a linear search, later we should make it \r
-     binary */\r
-  int i = pq->end;\r
-  while (i > pq->start &&\r
-         priority < pq->entries[i-1].priority) {\r
-    --i;\r
+  if (pq->end - pq->start < LARGE_QUEUE_SIZE) {\r
+    int i = pq->end;\r
+    while (i > pq->start &&\r
+           priority < pq->entries[i-1].priority) {\r
+      --i;\r
+    }\r
+    return i;\r
   }\r
+  else {\r
+    int lower = pq->start;\r
+    int upper = pq->end - 1;\r
+    while (1) {\r
+      int midpoint = (lower + upper) >> 1;\r
 \r
-  return i;\r
+      if (upper < lower)\r
+        return lower;\r
+      \r
+      if (priority < pq->entries[midpoint].priority) {\r
+        upper = midpoint - 1;\r
+        continue;\r
+      }\r
+      if (priority > pq->entries[midpoint].priority) {\r
+        lower = midpoint + 1;\r
+        continue;\r
+      }\r
+      while (midpoint < pq->end &&\r
+             priority == pq->entries[midpoint].priority) {\r
+        ++midpoint;\r
+      }\r
+      return midpoint;\r
+    }\r
+  }\r
 }\r
 \r
 int\r
@@ -478,12 +516,53 @@ int
 pq_find_item(poe_queue *pq, pq_id_t id, pq_priority_t priority) {\r
   int i;\r
 \r
-  for (i = pq->start; i < pq->end; ++i) {\r
-    if (pq->entries[i].id == id)\r
-      return i;\r
+  STATS(++pq->total_finds);\r
+  if (pq->end - pq->start < LARGE_QUEUE_SIZE) {\r
+    for (i = pq->start; i < pq->end; ++i) {\r
+      if (pq->entries[i].id == id)\r
+        return i;\r
+    }\r
+    DEBUG(fprintf(stderr, "pq_find_item %d => %f\n", id, priority) );\r
+    croak("Internal inconsistency: event should have been found");\r
+  }\r
+\r
+  /* try a binary search */\r
+  /* simply translated from the perl */\r
+  STATS(++pq->binary_finds);\r
+  {\r
+    int lower = pq->start;\r
+    int upper = pq->end - 1;\r
+    int linear_point;\r
+    while (1) {\r
+      int midpoint = (upper + lower) >> 1;\r
+      if (upper < lower) {\r
+        croak("Internal inconsistency, priorities out of order");\r
+      }\r
+      if (priority < pq->entries[midpoint].priority) {\r
+        upper = midpoint - 1;\r
+        continue;\r
+      }\r
+      if (priority > pq->entries[midpoint].priority) {\r
+        lower = midpoint + 1;\r
+        continue;\r
+      }\r
+      linear_point = midpoint;\r
+      while (linear_point >= pq->start &&\r
+             priority == pq->entries[linear_point].priority) {\r
+        if (pq->entries[linear_point].id == id)\r
+          return linear_point;\r
+        --linear_point;\r
+      }\r
+      linear_point = midpoint;\r
+      while ( (++linear_point < pq->end) &&\r
+              priority == pq->entries[linear_point].priority) {\r
+        if (pq->entries[linear_point].id == id)\r
+          return linear_point;\r
+      }\r
+\r
+      croak("internal inconsistency: event should have been found");\r
+    }\r
   }\r
-  DEBUG(fprintf(stderr, "pq_find_item %d => %f\n", id, priority) );\r
-  croak("Internal inconsistency: event should have been found");\r
 }\r
 \r
 int\r
@@ -720,6 +799,34 @@ pq_dump(poe_queue *pq) {
   hv_iterinit(pq->ids);\r
   while ((he = hv_iternext(pq->ids)) != NULL) {\r
     STRLEN len;\r
-    fprintf(stderr, "   %s => %f\n", HePV(he, len), SvNV(hv_iterval(pq->ids, he)));\r
+    fprintf(stderr, "   %d => %f\n", *(pq_id_t *)HePV(he, len), SvNV(hv_iterval(pq->ids, he)));\r
+  }\r
+}\r
+\r
+/*\r
+pq_verify - basic verification of the structure of the queue\r
+\r
+For now check for duplicate ids in sequence.\r
+*/\r
+void\r
+pq_verify(poe_queue *pq) {\r
+  int i;\r
+  int lastid;\r
+  int found_err = 0;\r
+\r
+  if (pq->start != pq->end) {\r
+    lastid = pq->entries[pq->start].id;\r
+    i = pq->start + 1;\r
+    while (i < pq->end) {\r
+      if (pq->entries[i].id == lastid) {\r
+        fprintf(stderr, "Duplicate id %d at %d\n", lastid, i);\r
+        ++found_err;\r
+      }\r
+      ++i;\r
+    }\r
+  }\r
+  if (found_err) {\r
+    pq_dump(pq);\r
+    exit(1);\r
   }\r
 }\r

diff --git a/queue.h b/queue.h
index 752069bbed08a59542497c8466cd1204806c70e6..036eb9ea71a2f4ebedd7264b343a35aa0e425277 100644 (file)
--- a/queue.h
+++ b/queue.h
@@ -35,5 +35,6 @@ pq_adjust_priority(poe_queue *pq, pq_id_t id, SV *filter, double delta, pq_prior
 extern int\r
 pq_peek_items(poe_queue *pq, SV *filter, int max_count, pq_entry **items);\r
 extern void pq_dump(poe_queue *pq);\r
+extern void pq_verify(poe_queue *pq);\r
 \r
 #endif\r