search

flandr / ccmetrics

Fine-grained application metrics for C++
1 stars 1 forks source link

Incomplete index towers are a problem #10

Closed flandr closed 9 years ago

flandr commented 9 years ago

// XXX double check that it's ok to fail: it is not ok to fail.

Marking the towers top-down can cause partitioning at a list level, reducing the effectiveness of the index lists:

T1, start linking node 1 w/ an incomplete tower:

+-+                              +-+
| +----------------------------> | |
+-+                              +-+

+-+                       +-+    +-+
| +--+                    |-|--> | |
+-+  |                    +-+    +-+
     v

+-+                       +-+    +-+
| +---------------------> | |--> | |
+-+                       +-+    +-+

(1)                       (9)    (10)

T2, fully link node 5, picking up the incomplete references from node 1

+-+        +-+                   +-+
| +------> | |-----------------> | |
+-+        +-+                   +-+

+-+        +-+            +-+    +-+
| +--+     | |--+         |-|--> | |
+-+  |     +-+  |         +-+    +-+
     v          v

+-+        +-+            +-+    +-+
| +--------| |----------> | |--> | |
+-+        +-+            +-+    +-+

(1)        (5)            (9)    (10)

T3 finishing linking node1, cutting off the middle level of node 5.

+-+        +-+                   +-+
| +------> | |-----------------> | |
+-+        +-+                   +-+
     +----------------+
+-+  |     +-+        |   +-+    +-+
| +--+     | |--+     +-> |-|--> | |
+-+        +-+  |         +-+    +-+
                v

+-+        +-+            +-+    +-+
| +--------| |----------> | |--> | |
+-+        +-+            +-+    +-+

(1)        (5)            (9)    (10)

This is not a correctness issue (except that currently it loses a reference, leaking node 5); the invariants for the level-0 list are preserved. It is confusing, tho.

Ideally we would form towers bottom-up, preventing the observation of the lower levels of partially-completed towers. Unfortunately there is no way to do this with a finite set of hazard pointers, except with n*log(n) cost of repeated calls to find.

flandr commented 9 years ago

Resolved, though with some sadness.