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