Re: run flags vs active intervals


Larry Gritz <l...@...>
 

OK, so what do we make of all this? I've quoted a few interesting cases below.


Most of the unique state patterns look like this, typical sparse runflags from secondary ray batches: runflags are awful, they spend too much time on points that are "off" (and the bigger the batches are, the more runflags suck). Either spans or indices are a HUGE speedup (2-8x, depending on batch size), with indices being about 20% faster than spans.

runflags 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
span 0 1 93 95 102 103 146 147 191 192
indices 0 93 94 102 146 191

runflags: 18.31
spans: 2.15
indices: 1.72


runflags 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
span 0 1 64 65
indices 0 64

runflags: 5.21
spans: 1.10
indices: 0.91


runflags 1 0 0 0 0 0 0 0 0 0 1
span 0 1 10 11
indices 0 10

runflags: 1.76
spans: 1.11
indices: 0.91

But when npoints is sufficiently small, runflags wins (though indices are VERY close in speed):


runflags 1 0 0 1
span 0 1 3 4
indices 0 3

runflags: 0.88
spans: 1.11
indices: 0.91

runflags 1 0 1
span 0 1 2 3
indices 0 2

runflags: 0.86
spans: 1.11
indices: 0.91

The very common case of a single point on:

runflags 1
span 0 1
indices 0

runflags: 0.68
spans: 0.84
indices: 0.75

In typical inside-conditional states or fairly coherent secondaries, indices are the clear winner, even beating spans handily:

runflags 1 0 1 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 1 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 1 0 1
span 0 1 2 3 5 7 9 12 15 16 18 21 22 24 25 27 28 29 31 36 41 42 43 46 47 48 49 50 51 53 54 57 60 61 64 65 67 68 71 72 73 74 75 79 85 87 89 92 96 98 99 100 103 104 106 107 112 116 117 118
indices 0 2 5 6 9 10 11 15 18 19 20 22 23 25 26 28 31 32 33 34 35 41 43 44 45 47 49 51 52 54 55 56 60 64 67 71 73 75 76 77 78 85 86 89 90 91 96 97 99 103 106 112 113 114 115 117

runflags: 36.97
spans: 23.11
indices: 11.66


runflags 1 0 1 1 1 1 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 1
span 0 1 2 6 10 11 13 16 23 24 27 29 32 33 37 39 40 43 46 48 52 54 62 65 66 67 68 69 72 73 74 77 78 79 80 81
indices 0 2 3 4 5 10 13 14 15 23 27 28 32 37 38 40 41 42 46 47 52 53 62 63 64 66 68 72 74 75 76 78 80

runflags: 20.25
spans: 13.32
indices: 7.15

But for long spans of 1's, which are very rare for secondaries but dominate primary batches, spans are the fastest and indices the slowest:


runflags 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
span 0 2 3 23 24 42 43 61
indices 0 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

runflags: 10.07
spans: 9.22
indices: 12.09


runflags 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
span 0 16
indices 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

runflags: 2.86
spans: 2.73
indices: 3.72


runflags 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 1 0 0 1 1 1 1 1
span 0 16 17 22 23 27 29 32 33 34 36 41
indices 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 18 19 20 21 23 24 25 26 29 30 31 33 36 37 38 39 40

runflags: 8.90
spans: 8.39
indices: 7.31




runflags 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
span 0 48
indices 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

runflags: 7.54
spans: 7.14
indices: 10.08


runflags 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
span 0 102
indices 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

runflags: 15.89
spans: 13.90
indices: 21.14
--
Larry Gritz
l...@...

Join osl-dev@lists.aswf.io to automatically receive all group messages.