Joshua ben Jore > Runops-Trace-0.14 > TODO


Annotate this POD


New  1
Open  1
View/Report Bugs

Hot path detection using decaying bloom filters ^

Instead of using a hash of pointer to counter, implement the following:

        - allocate a bitfield of size N. More bits = more accuracy. Maybe look into
          dynamic bloom filters, to accomodate growing optree. Not really

        - prepare K hash functions (simple galois field multiplications over random
          primes or sth)

        - for every opcode address that matches the opmask, apply:

                bitfield, bloom_fill;
                do {
                        bitoffset = hash(i++, ptr); /* ptr is a CV or a PL_op */
                } while ( i < k && bitfield[bitoffset] );

                if ( i < k ) {
                        if ( ++bloom_fill > max_fill ) {
                                /* if the bloom filter is too full implement random decay */
                                for ( i = 0; i < chunk; i ++ ) {
                                        bitfield[random] = 0;

                        /* finally set the bit for hash(k, PL_op */
                        bitfield[bitoffset] = 1;
                } else {
                        /* opcode exceeded threshold, execute trigger */

                The bloom filter is a constant size, relatively low overhead
                alternative to a hash, which can produce false positives, but
                not false negative. The hot path is pretty much guaranteed to be found,
                but a cold path could be mis identified as a hot path.

                By adding decaying when the bloom filter is too full we can dynamically
                identify a changing hot path.

                Guesstimating that a pretty large (accurate) bloom filter with K at
                around 3-4 and max_fill set fairly low should provide good results with
                relatively low overhead.

CV tracing ^

Allow conditional tracing of ENTERSUB based on the CV it will invoke, instead of/in addition to the PL_op of the ENTERSUB.

syntax highlighting: