Line data Source code
1 : #ifndef HEADER_fd_src_ballet_pack_fd_pack_bitset_h
2 : #define HEADER_fd_src_ballet_pack_fd_pack_bitset_h
3 :
4 : /* One of the main computational tasks of fd_pack is determining whether
5 : a given transaction conflicts with a different transaction or a group
6 : of transactions. This is just a set intersection problem, and there
7 : are many ways to represent sets. Here, we have the additional
8 : hypothesis that accounts referenced in a transaction exhibit some
9 : kind of power law probability distribution, i.e. certain accounts are
10 : referenced much more frequently than other accounts. This means if
11 : two transactions conflict, the account that causes them to conflict
12 : is not a uniform random choice.
13 :
14 : This non-uniformity motivates the use of a hybrid bitset/hashset
15 : representation. In an ideal world, we'd represent the N most common
16 : accounts with a bit in fixed-size a bitset and the rest in a hashset.
17 : To produce the bitset, we'd have some kind of mapping off on the side
18 : of which accounts correspond to which bits, and the intersection
19 : could be computed just looking at the bitset in the common case.
20 :
21 : However, the N most common accounts can change, and the complexity of
22 : tracking down every bitset that needs to be adjusted when the N most
23 : common accounts changes seems like it would eliminate any of the
24 : gains from this approach.
25 :
26 : Instead, we implement a simpler version of this idea. We reserve a
27 : bit for an account when we have two transactions that reference that
28 : account. Note that an account which appears in a single transaction
29 : can't cause a conflict, and this means that we only have one bitset
30 : to update.
31 :
32 : On the flip side, we'd like to free the bit when the reference count
33 : drops from 2 to 1, but again we face the difficult problem of
34 : tracking down that single transaction. Threading some kind of
35 : per-account linked list through the transactions would work but seems
36 : like a nightmare, so we just defer freeing the bit until the
37 : reference count drops to 0.
38 :
39 : Since our bitset is fixed size, it's possible that we may try to
40 : reserve a bit but find all our bits are already mapped. Rather than
41 : spilling the account to some kind of overflow hashset like in the
42 : motivating sketch solution, we just don't store it. That means that
43 : this compressed set representation can sometimes answer incorrectly,
44 : but only in one direction: it may suggest a transaction doesn't
45 : conflict when it actually does. This may seem like the opposite type
46 : of error compared to what we want, but for each transaction we might
47 : accept into the microblock, we need to iterate over at least the
48 : writable accounts it contains to check if they would exceed the
49 : per-account max write lock cost, so we already have a case of needing
50 : to reject a transaction it seemed like we might accept, so now we
51 : just have a second reason for that.
52 :
53 : It is easy to modify the code slightly to flip the direction of the
54 : error (i.e. it might say two sets intersect when they actually
55 : don't) by permanently reserving one of the bits as an "overflow bit"
56 : indicating that the transaction has some accounts other than those
57 : represented in the bitset. This naturally causes any transaction
58 : with the overflow bit to conflict with any other transaction with the
59 : overflow bit.
60 :
61 : All of this can be done with AVX or with fd_set. */
62 :
63 : #ifndef FD_PACK_BITSET_MODE
64 : # if FD_HAS_AVX512
65 : # define FD_PACK_BITSET_MODE 2
66 : # elif FD_HAS_AVX
67 : # define FD_PACK_BITSET_MODE 1
68 : # else
69 : # define FD_PACK_BITSET_MODE 0
70 : # endif
71 : #endif
72 :
73 522 : #define FD_PACK_BITSET_SLOWPATH ((ushort)0xFFFF)
74 12791091 : #define FD_PACK_BITSET_FIRST_INSTANCE ((ushort)0xFFFE)
75 : /* Define a little interface for the different bitset implementations.
76 :
77 : FD_PACK_BITSET_T is never used in the code, but is the type of the
78 : arguments to the other functions.
79 :
80 : FD_PACK_BITSET_MAX is the number of elements that can be stored in
81 : the bitset.
82 :
83 : FD_PACK_BITSET_DECLARE declares a variable called `name` of type T (or
84 : something that decays to T). The set has indeterminate value at this
85 : point.
86 :
87 : FD_PACK_BITSET_CLEAR takes a set of type T and clears it, setting
88 : `set` to the empty set.
89 :
90 : FD_PACK_BITSET_SETN sets bit n in the set. `set` must be type T. If
91 : n is not in [0, FD_PACK_BITSET_MAX) or n is already in `set`, this is
92 : a no-op.
93 :
94 : FD_PACK_BITSET_CLEARN clears bit n in the set. `set` must be type T.
95 : If n is not in [0, FD_PACK_BITSET_MAX) or n is not in `set`, this is
96 : a no-op.
97 :
98 : FD_PACK_BITSET_OR updates srcdest with the union of srcdest and x.
99 : This is a statement and so does not return anything, not a value.
100 : Think of it like srcdest |= x.
101 :
102 : FD_PACK_BITSET_INTERSECT4_EMPTY returns whether (x1 & y1) and
103 : (x2 & y2) are both empty. It is done this way because fd_set
104 : temporaries are a bit of a pain. All 4 sets should be of type T.
105 : Does not modify any of the input sets.
106 :
107 : FD_PACK_BITSET_ISNULL takes a set of type T and returns 1 if the set
108 : is empty/the null set and 0 if it has at least one element.
109 :
110 : FD_PACK_BITSET_COPY takes two sets of type T and resets the contents
111 : of dest to be equal to the contents of src. */
112 : #if FD_PACK_BITSET_MODE==0
113 :
114 :
115 : # define SET_NAME addr_bitset
116 : /* We actually have some flexibility in this case, but for the few
117 : blocks that I looked it, 256 seemed like a good number for 1024
118 : transactions. */
119 : # define SET_MAX 256
120 : # include "../../util/tmpl/fd_set.c"
121 :
122 : # define FD_PACK_BITSET_T addr_bitset_t * /* == ulong * */
123 : # define FD_PACK_BITSET_MAX 256UL
124 :
125 : # define FD_PACK_BITSET_DECLARE(name) addr_bitset_t name [ addr_bitset_word_cnt ]
126 : # define FD_PACK_BITSET_CLEAR(set) addr_bitset_new( set )
127 : # define FD_PACK_BITSET_SETN(set, n) do { \
128 : if( n<FD_PACK_BITSET_MAX ) addr_bitset_insert( set, n ); \
129 : } while( 0 )
130 : # define FD_PACK_BITSET_CLEARN(set, n) do { \
131 : if( n<FD_PACK_BITSET_MAX ) addr_bitset_remove( set, n ); \
132 : } while( 0 )
133 : # define FD_PACK_BITSET_OR(srcdest, x) do { \
134 : addr_bitset_t * __srcdest = (srcdest); \
135 : addr_bitset_union( __srcdest, __srcdest, (x) ); \
136 : } while( 0 )
137 : # define FD_PACK_BITSET_INTERSECT4_EMPTY(x1, x2, y1, y2) (__extension__({ \
138 : addr_bitset_t __temp1[ addr_bitset_word_cnt ]; \
139 : addr_bitset_t __temp2[ addr_bitset_word_cnt ]; \
140 : addr_bitset_intersect( __temp1, (x1), (y1) ); \
141 : addr_bitset_intersect( __temp2, (x2), (y2) ); \
142 : addr_bitset_is_null( __temp1 ) && addr_bitset_is_null( __temp2 ); \
143 : }))
144 : # define FD_PACK_BITSET_ISNULL(set) addr_bitset_is_null( set )
145 :
146 : # define FD_PACK_BITSET_COPY(dest, src) addr_bitset_copy( dest, src )
147 :
148 :
149 : #elif FD_PACK_BITSET_MODE==1
150 :
151 : # include "../../util/simd/fd_avx.h"
152 :
153 : # define FD_PACK_BITSET_T wv_t
154 13997648 : # define FD_PACK_BITSET_MAX 256UL
155 :
156 3937160 : # define FD_PACK_BITSET_DECLARE(name) wv_t name
157 17773296 : # define FD_PACK_BITSET_CLEAR(set) (set) = wv_zero()
158 20769044 : # define FD_PACK_BITSET_SETN(set, n) do { \
159 20769044 : wv_t _n = wv_bcast( n ); \
160 20769044 : wv_t shift_offset = wv( 0UL, 64UL, 128UL, 192UL ); \
161 20769044 : wv_t one = wv_bcast( 1UL ); \
162 20769044 : set = wv_or( set, wv_shl_vector( one, wv_sub( _n, shift_offset ) ) ); \
163 20769044 : } while( 0 )
164 27102604 : # define FD_PACK_BITSET_CLEARN(set, n) do { \
165 27102604 : wv_t _n = wv_bcast( n ); \
166 27102604 : wv_t shift_offset = wv( 0UL, 64UL, 128UL, 192UL ); \
167 27102604 : wv_t one = wv_bcast( 1UL ); \
168 27102604 : set = wv_andnot( wv_shl_vector( one, wv_sub( _n, shift_offset ) ), set ); \
169 27102604 : } while( 0 )
170 17436996 : # define FD_PACK_BITSET_OR(srcdest, x) srcdest = wv_or( srcdest, x );
171 : # define FD_PACK_BITSET_INTERSECT4_EMPTY(x1, x2, y1, y2) (__extension__({ \
172 : wv_t _temp = wv_or( wv_and( x1, y1 ), wv_and( x2, y2 ) ); \
173 : _mm256_testz_si256( _temp, _temp ); \
174 : }))
175 : # define FD_PACK_BITSET_ISNULL(set) _mm256_testz_si256( set, set )
176 5935076 : # define FD_PACK_BITSET_COPY(dest, src) dest=src
177 :
178 : #elif FD_PACK_BITSET_MODE==2
179 : # include "../../util/simd/fd_avx512.h"
180 :
181 : # define FD_PACK_BITSET_T wwv_t
182 7044392 : # define FD_PACK_BITSET_MAX 512UL
183 :
184 1968580 : # define FD_PACK_BITSET_DECLARE(name) wwv_t name
185 8886648 : # define FD_PACK_BITSET_CLEAR(set) (set) = wwv_zero()
186 10435594 : # define FD_PACK_BITSET_SETN(set, n) do { \
187 10435594 : wwv_t _n = wwv_bcast( n ); \
188 10435594 : wwv_t shift_offset = wwv( 0UL, 64UL, 128UL, 192UL, 256UL, 320UL, 384UL, 448UL ); \
189 10435594 : wwv_t one = wwv_bcast( 1UL ); \
190 10435594 : set = wwv_or( set, wwv_shl_vector( one, wwv_sub( _n, shift_offset ) ) ); \
191 10435594 : } while( 0 )
192 13749702 : # define FD_PACK_BITSET_CLEARN(set, n) do { \
193 13749702 : wwv_t _n = wwv_bcast( n ); \
194 13749702 : wwv_t shift_offset = wwv( 0UL, 64UL, 128UL, 192UL, 256UL, 320UL, 384UL, 448UL ); \
195 13749702 : wwv_t one = wwv_bcast( 1UL ); \
196 13749702 : set = wwv_andnot( wwv_shl_vector( one, wwv_sub( _n, shift_offset ) ), set ); \
197 13749702 : } while( 0 )
198 8718754 : # define FD_PACK_BITSET_OR(srcdest, x) srcdest = wwv_or( srcdest, x );
199 : # define FD_PACK_BITSET_INTERSECT4_EMPTY(x1, x2, y1, y2) (__extension__({ \
200 : wwv_t _temp = wwv_or( wwv_and( x1, y1 ), wwv_and( x2, y2 ) ); \
201 : _mm512_test_epi64_mask( _temp, _temp )==0; \
202 : }))
203 : # define FD_PACK_BITSET_ISNULL(set) (0==_mm512_test_epi64_mask( set, set ))
204 2967794 : # define FD_PACK_BITSET_COPY(dest, src) dest=src
205 :
206 : #else
207 : # error "FD_PACK_BITSET_MODE not recognized"
208 : #endif
209 :
210 : #endif /* HEADER_fd_src_ballet_pack_fd_pack_bitset_h */
|
