1 | #!/usr/bin/env bash
|
2 | #
|
3 | # Test sparse array
|
4 | #
|
5 | # Relevant files:
|
6 | #
|
7 | # test/ble-idioms.test.sh
|
8 | #
|
9 | # core/shell.py defines these functions:
|
10 | # _a2sp
|
11 | # _d2sp
|
12 | # _opsp
|
13 | # builtin/func_misc.py is where they are implemented
|
14 | #
|
15 | # core/value.asdl defines value.{BashArray,SparseArray}
|
16 | #
|
17 | # _gen/core/value.asdl.* - generated from value.asdl
|
18 | #
|
19 | # _gen/bin/oils_for_unix.mycpp.cc has the translation of
|
20 |
|
21 | #
|
22 | # Usage:
|
23 | # demo/sparse-array.sh <function name>
|
24 |
|
25 | TIMEFORMAT='%U'
|
26 |
|
27 | set -o nounset
|
28 | set -o pipefail
|
29 | set -o errexit
|
30 |
|
31 | my-time() {
|
32 | local tmp=/tmp/sparse-array
|
33 | { time "$@"; } 2> $tmp
|
34 | echo "$(cat $tmp) seconds"
|
35 | }
|
36 |
|
37 | compare-x() {
|
38 | local x=$1
|
39 |
|
40 | local osh=_bin/cxx-opt/osh
|
41 | ninja $osh
|
42 |
|
43 | echo ===
|
44 | echo $osh SparseArray
|
45 | echo
|
46 | my-time sparse-$x $osh
|
47 |
|
48 | for sh in bash $osh; do
|
49 | echo ===
|
50 | echo $sh
|
51 | echo
|
52 | my-time $sh $0 $x
|
53 | done
|
54 | }
|
55 |
|
56 | compare-sum-shift() {
|
57 | compare-x sum-shift
|
58 | }
|
59 |
|
60 | compare-append-sparse() {
|
61 | compare-x append-sparse
|
62 | }
|
63 |
|
64 | compare-append-dense() {
|
65 | compare-x append-dense
|
66 | }
|
67 |
|
68 | #
|
69 | # Workloads
|
70 | #
|
71 |
|
72 | sum-shift() {
|
73 | local n=${1:-1000}
|
74 |
|
75 | # Populate array 0 .. n-1
|
76 | a=()
|
77 | for (( i = 0; i < n; ++i )); do
|
78 | a+=( $i )
|
79 | #a+=( 1 )
|
80 | done
|
81 | #echo "${a[@]}"
|
82 |
|
83 | # Quadratic loop: sum all numbers, shift by 1
|
84 | local sum=0
|
85 | while true; do
|
86 | local len=${#a[@]}
|
87 | if test $len -eq 0; then
|
88 | break
|
89 | fi
|
90 |
|
91 | for (( i = 0; i < len; ++i )); do
|
92 | sum=$(( sum + ${a[i]} ))
|
93 | done
|
94 |
|
95 | #echo sum=$sum
|
96 |
|
97 | # Shift
|
98 | a=( ${a[@]:1} )
|
99 | done
|
100 |
|
101 | echo sum=$sum
|
102 | }
|
103 |
|
104 | sparse-sum-shift() {
|
105 | local osh=$1
|
106 |
|
107 | $osh <<'EOF'
|
108 | shopt --set ysh:upgrade
|
109 |
|
110 | f() {
|
111 | local n=${1:-1000}
|
112 |
|
113 | a=()
|
114 | var sp = _a2sp(a) # empty sparse array
|
115 |
|
116 | # Populate SparseArray 0 .. n-1
|
117 | for (( i = 0; i < n; ++i )); do
|
118 | to_append=( $i )
|
119 | call _opsp(sp, 'append', to_append)
|
120 | done
|
121 |
|
122 | #echo "${a[@]}"
|
123 | echo "length $[_opsp(sp, 'len')]"
|
124 | #echo SUBST @[_opsp(sp, 'subst')]
|
125 | #echo KEYS @[_opsp(sp, 'keys')]
|
126 |
|
127 | var sum = 0
|
128 |
|
129 | while (true) {
|
130 | var length = _opsp(sp, 'len')
|
131 | if (length === 0) {
|
132 | break
|
133 | }
|
134 |
|
135 | #echo ZERO $sum $[_opsp(sp, 'get', 0)]
|
136 | #echo ONE $sum $[_opsp(sp, 'get', 1)]
|
137 | for i in (0 .. length) {
|
138 | setvar sum += _opsp(sp, 'get', i)
|
139 | }
|
140 |
|
141 | #echo sum=$sum
|
142 |
|
143 | # Slice to BashArray
|
144 | var a = _opsp(sp, 'slice', 1, length)
|
145 |
|
146 | # Convert back - is this slow?
|
147 | setvar sp = _a2sp(a)
|
148 | }
|
149 |
|
150 | echo sum=$sum
|
151 | }
|
152 |
|
153 | f
|
154 |
|
155 | EOF
|
156 | }
|
157 |
|
158 | append-sparse() {
|
159 | local n=${1:-24} # up to 2^n
|
160 | local m=${2:-2000}
|
161 |
|
162 | to_append=( $(seq $m) ) # split words
|
163 |
|
164 | a=()
|
165 | for (( i = 0; i < n; ++i )) {
|
166 | a[$(( 1 << i ))]=$i
|
167 | a+=( ${to_append[@]} )
|
168 | }
|
169 | #echo ${a[@]}
|
170 | #echo ${!a[@]}
|
171 | echo ${#a[@]}
|
172 | }
|
173 |
|
174 | sparse-append-sparse() {
|
175 | local osh=${1:-_bin/cxx-opt/osh}
|
176 | local n=${2:-24}
|
177 | local m=${3:-2000}
|
178 |
|
179 | NUM_ITERS=$n TO_APPEND=$m $osh <<'EOF'
|
180 | n=$NUM_ITERS
|
181 | m=$TO_APPEND
|
182 | to_append=( $(seq $m) ) # split words before ysh:upgrade
|
183 |
|
184 |
|
185 | shopt --set ysh:upgrade
|
186 |
|
187 | f() {
|
188 | a=()
|
189 | var sp = _a2sp(a)
|
190 |
|
191 | for (( i = 0; i < n; ++i )) {
|
192 | call _opsp(sp, 'set', 1 << i, str(i))
|
193 | call _opsp(sp, 'append', to_append)
|
194 |
|
195 | #time call _opsp(sp, 'append', to_append)
|
196 | #echo $[_opsp(sp, 'len')]
|
197 | #echo
|
198 | }
|
199 | echo $[_opsp(sp, 'len')]
|
200 | #echo @[_opsp(sp, 'subst')]
|
201 | #echo @[_opsp(sp, 'keys')]
|
202 | }
|
203 |
|
204 | f
|
205 | EOF
|
206 | }
|
207 |
|
208 | append-dense() {
|
209 | local n=${1:-24} # up to 2^n
|
210 | local m=${2:-2000}
|
211 |
|
212 | to_append=( $(seq $m) ) # split words
|
213 |
|
214 | a=()
|
215 | for (( i = 0; i < n; ++i )) {
|
216 | a+=( ${to_append[@]} )
|
217 | }
|
218 | #echo ${a[@]}
|
219 | #echo ${!a[@]}
|
220 | echo ${#a[@]}
|
221 | }
|
222 |
|
223 | sparse-append-dense() {
|
224 | local osh=${1:-_bin/cxx-opt/osh}
|
225 | local n=${2:-24}
|
226 | local m=${3:-2000}
|
227 |
|
228 | NUM_ITERS=$n TO_APPEND=$m $osh <<'EOF'
|
229 | n=$NUM_ITERS
|
230 | m=$TO_APPEND
|
231 | to_append=( $(seq $m) ) # split words before ysh:upgrade
|
232 |
|
233 | shopt --set ysh:upgrade
|
234 |
|
235 | f() {
|
236 | a=()
|
237 | var sp = _a2sp(a)
|
238 |
|
239 | for (( i = 0; i < n; ++i )) {
|
240 | #call _opsp(sp, 'set', 1 << i, str(i))
|
241 | call _opsp(sp, 'append', to_append)
|
242 |
|
243 | #time call _opsp(sp, 'append', to_append)
|
244 | #echo $[_opsp(sp, 'len')]
|
245 | #echo
|
246 | }
|
247 | echo $[_opsp(sp, 'len')]
|
248 | #echo @[_opsp(sp, 'subst')]
|
249 | #echo @[_opsp(sp, 'keys')]
|
250 | }
|
251 |
|
252 | f
|
253 | EOF
|
254 | }
|
255 |
|
256 | demo() {
|
257 | # Compiles faster
|
258 | #local osh=_bin/cxx-asan/osh
|
259 |
|
260 | local osh=_bin/cxx-opt/osh
|
261 |
|
262 | ninja $osh
|
263 |
|
264 | $osh <<'EOF'
|
265 |
|
266 | # Create regular bash array
|
267 |
|
268 | a=( {1..100} )
|
269 | a[1000]='sparse'
|
270 | echo $[type(a)]
|
271 |
|
272 | # Time O(n^2) slicing in a loop
|
273 |
|
274 | time while true; do
|
275 | # Convert it to the Dict[BigInt, str] representation
|
276 | var sp = _a2sp(a)
|
277 | #echo $[type(sp)]
|
278 |
|
279 | var len = _opsp(sp, 'len')
|
280 | #echo "sparse length $len"
|
281 |
|
282 | setvar a = _opsp(sp, 'slice', 1, 2000)
|
283 | #echo "array length ${#a[@]}"
|
284 | echo "array ${a[@]}"
|
285 |
|
286 | if test ${#a[@]} -eq 0; then
|
287 | break
|
288 | fi
|
289 | done
|
290 | EOF
|
291 |
|
292 | return
|
293 |
|
294 | # Copied from spec/ble-idioms.test.sh
|
295 | $osh <<'EOF'
|
296 |
|
297 | a=( foo {25..27} bar )
|
298 |
|
299 | a[10]='sparse'
|
300 |
|
301 | var sp = _a2sp(a)
|
302 | echo $[type(sp)]
|
303 |
|
304 | echo len: $[_opsp(sp, 'len')]
|
305 |
|
306 | #echo $[len(sp)]
|
307 |
|
308 | shopt -s ysh:upgrade
|
309 |
|
310 | echo subst: @[_opsp(sp, 'subst')]
|
311 | echo keys: @[_opsp(sp, 'keys')]
|
312 |
|
313 | echo slice: @[_opsp(sp, 'slice', 2, 5)]
|
314 |
|
315 | call _opsp(sp, 'set', 0, 'set0')
|
316 |
|
317 | echo get0: $[_opsp(sp, 'get', 0)]
|
318 | echo get1: $[_opsp(sp, 'get', 1)]
|
319 |
|
320 | to_append=(x y)
|
321 | call _opsp(sp, 'append', to_append)
|
322 | echo subst: @[_opsp(sp, 'subst')]
|
323 | echo keys: @[_opsp(sp, 'keys')]
|
324 |
|
325 | echo ---
|
326 |
|
327 | # Sparse
|
328 | var d = {
|
329 | '1': 'a',
|
330 | '10': 'b',
|
331 | '100': 'c',
|
332 | '1000': 'd',
|
333 | '10000': 'e',
|
334 | '100000': 'f',
|
335 | }
|
336 |
|
337 | var sp2 = _d2sp(d)
|
338 |
|
339 | echo len: $[_opsp(sp2, 'len')]
|
340 | echo subst: @[_opsp(sp2, 'subst')]
|
341 |
|
342 | EOF
|
343 |
|
344 | }
|
345 |
|
346 | "$@"
|