Skip to content

Instantly share code, notes, and snippets.

@ko1 ko1/_report.md

Last active Nov 8, 2016
Embed
What would you like to do?

Report about rb_id_table performance evaluation

Ruby 2.3 introduced special table which only have ID keys (limited to 32bit). Also this table deos not keep ordering information. These two specification can improve performance than ID table.

Now we have several implementation so I tried to evaluate performance like https://bugs.ruby-lang.org/issues/12142.

Conclusion

This is my conclusion.

  • For performance, ffalcon (22) is the best.
  • For table size, ffalcon (22) consumes more. But performance gain can allow dis advantage.

memory size

size_all_16 size_all_32 size_all_64 size_all_128 size_all_256 size_all_

size_vs_ffalcon_16 size_vs_ffalcon_32 size_vs_ffalcon_64 size_vs_ffalcon_128 size_vs_ffalcon_256 size_vs_ffalcon_

performance

All implementations

id_table_all_hit_16 id_table_all_hit_32 id_table_all_hit_64 id_table_all_hit_128 id_table_all_hit_256

id_table_all_miss_16 id_table_all_miss_32 id_table_all_miss_64 id_table_all_miss_128 id_table_all_miss_256

v.s. ffalcon's implementation

id_table_vs_ffalcon_hit_16 id_table_vs_ffalcon_hit_32 id_table_vs_ffalcon_hit_64 id_table_vs_ffalcon_hit_128 id_table_vs_ffalcon_hit_256

id_table_vs_ffalcon_miss_16 id_table_vs_ffalcon_miss_32 id_table_vs_ffalcon_miss_64 id_table_vs_ffalcon_miss_128 id_table_vs_ffalcon_miss_256

str = <<EOS
0 st
11 ary
12 ary_serial
13 ary_serial_swap
14 ary_serial_sort
15 ary_serial_sort2
21 ffalcon
22 ffalcon2
31 mix32_1
32 mix32_2
33 mix64_1
34 mix64_2
35 mix64_3
EOS
NAMES = str.lines.each_with_object({}){|line, r| n, name = line.strip.split(' '); r[n] = "#{name} (#{n})"}
require 'csv'
def label_str l
l.gsub('_', '\_')
end
def plot ps
IO.popen('gnuplot', 'a+'){|io|
io.puts ps.join("\n")
io.close_write
}
# puts ps.join("\n")
end
def plot_result files, name, hit, size
ps = []
ps << 'set datafile separator ","'
ps << 'set terminal png size 1280,480'
ps << "set out '#{name}_#{size}.png'"
ps << 'set xlabel "table size"'
ps << 'set ylabel "execution time (sec)"'
ps << "set title '#{label_str(name)} (#{size})'"
ps << 'set origin 0,0'
ps << "set xrange[0:#{size}]"
ps << 'set key outside'
col = hit == :hit ? 2 : 3
lines = []
files.each{|file|
raise unless /trunk.(\d+).small.csv/ =~ file
name = NAMES[$1]
lines << "'#{file}' using 1:#{col} with linespoints title '#{label_str(name)}'"
}
ps << "plot #{lines.join(', ')}"
plot ps
end
def plot_size files, name, max
ps = []
ps << 'set datafile separator ","'
ps << 'set terminal png size 1280,480'
ps << "set out '#{name}_#{max}.png'"
ps << 'set xlabel "table size"'
ps << 'set ylabel "size (B)"'
ps << "set title '#{label_str(name)} (#{max || 'no limit'})'"
ps << 'set origin 0,0'
ps << "set xrange[0:#{max}]" if max
ps << 'set key outside'
lines = []
files.each{|file|
raise unless /size_trunk.(\d+).csv/ =~ file
name = NAMES[$1]
lines << "'#{file}' using 1:2 with linespoints title '#{label_str(name)}'"
}
ps << "plot #{lines.join(', ')}"
plot ps
end
{ 'id_table_vs_ffalcon' => %w(trunk.22.small.csv trunk.34.small.csv),
'id_table_all' => Dir.glob('trunk.*.csv')}.each{|name, files|
[:hit, :miss].each{|hit|
[16, 32, 64, 128, 256].each{|max|
plot_result files, "#{name}_#{hit}", hit, max
}
}
}
{ 'size_all' => Dir.glob('size*.csv'),
'size_vs_ffalcon' => %w(size_trunk.22.csv size_trunk.34.csv)}.each{|name, files|
[16, 32, 64, 128, 256, nil].each{|size|
plot_size files, "#{name}", size
}
}
__END__
Dir.glob('result*.csv'){|file|
plot_result file, true
plot_result file, false
}
0 176
1 176
2 176
3 176
4 176
5 272
6 272
7 272
8 272
9 464
10 464
11 464
12 464
13 464
14 464
15 464
16 464
17 912
18 912
19 912
20 912
21 912
22 912
23 912
24 912
25 912
26 912
27 912
28 912
29 912
30 912
31 912
32 912
33 1744
34 1744
35 1744
36 1744
37 1744
38 1744
39 1744
40 1744
41 1744
42 1744
43 1744
44 1744
45 1744
46 1744
47 1744
48 1744
49 1744
50 1744
51 1744
52 1744
53 1744
54 1744
55 1744
56 1744
57 1744
58 1744
59 1744
60 1744
61 1744
62 1744
63 1744
64 1744
65 3408
66 3408
67 3408
68 3408
69 3408
70 3408
71 3408
72 3408
73 3408
74 3408
75 3408
76 3408
77 3408
78 3408
79 3408
80 3408
81 3408
82 3408
83 3408
84 3408
85 3408
86 3408
87 3408
88 3408
89 3408
90 3408
91 3408
92 3408
93 3408
94 3408
95 3408
96 3408
97 3408
98 3408
99 3408
100 3408
101 3408
102 3408
103 3408
104 3408
105 3408
106 3408
107 3408
108 3408
109 3408
110 3408
111 3408
112 3408
113 3408
114 3408
115 3408
116 3408
117 3408
118 3408
119 3408
120 3408
121 3408
122 3408
123 3408
124 3408
125 3408
126 3408
127 3408
128 3408
129 7248
130 7248
131 7248
132 7248
133 7248
134 7248
135 7248
136 7248
137 7248
138 7248
139 7248
140 7248
141 7248
142 7248
143 7248
144 7248
145 7248
146 7248
147 7248
148 7248
149 7248
150 7248
151 7248
152 7248
153 7248
154 7248
155 7248
156 7248
157 7248
158 7248
159 7248
160 7248
161 7248
162 7248
163 7248
164 7248
165 7248
166 7248
167 7248
168 7248
169 7248
170 7248
171 7248
172 7248
173 7248
174 7248
175 7248
176 7248
177 7248
178 7248
179 7248
180 7248
181 7248
182 7248
183 7248
184 7248
185 7248
186 7248
187 7248
188 7248
189 7248
190 7248
191 7248
192 7248
193 7248
194 7248
195 7248
196 7248
197 7248
198 7248
199 7248
200 7248
201 7248
202 7248
203 7248
204 7248
205 7248
206 7248
207 7248
208 7248
209 7248
210 7248
211 7248
212 7248
213 7248
214 7248
215 7248
216 7248
217 7248
218 7248
219 7248
220 7248
221 7248
222 7248
223 7248
224 7248
225 7248
226 7248
227 7248
228 7248
229 7248
230 7248
231 7248
232 7248
233 7248
234 7248
235 7248
236 7248
237 7248
238 7248
239 7248
240 7248
241 7248
242 7248
243 7248
244 7248
245 7248
246 7248
247 7248
248 7248
249 7248
250 7248
251 7248
252 7248
253 7248
254 7248
255 7248
256 7248
257 14416
258 14416
259 14416
260 14416
261 14416
262 14416
263 14416
264 14416
265 14416
266 14416
267 14416
268 14416
269 14416
270 14416
271 14416
272 14416
273 14416
274 14416
275 14416
276 14416
277 14416
278 14416
279 14416
280 14416
281 14416
282 14416
283 14416
284 14416
285 14416
286 14416
287 14416
288 14416
289 14416
290 14416
291 14416
292 14416
293 14416
294 14416
295 14416
296 14416
297 14416
298 14416
299 14416
300 14416
301 14416
302 14416
303 14416
304 14416
305 14416
306 14416
307 14416
308 14416
309 14416
310 14416
311 14416
312 14416
313 14416
314 14416
315 14416
316 14416
317 14416
318 14416
319 14416
320 14416
321 14416
322 14416
323 14416
324 14416
325 14416
326 14416
327 14416
328 14416
329 14416
330 14416
331 14416
332 14416
333 14416
334 14416
335 14416
336 14416
337 14416
338 14416
339 14416
340 14416
341 14416
342 14416
343 14416
344 14416
345 14416
346 14416
347 14416
348 14416
349 14416
350 14416
351 14416
352 14416
353 14416
354 14416
355 14416
356 14416
357 14416
358 14416
359 14416
360 14416
361 14416
362 14416
363 14416
364 14416
365 14416
366 14416
367 14416
368 14416
369 14416
370 14416
371 14416
372 14416
373 14416
374 14416
375 14416
376 14416
377 14416
378 14416
379 14416
380 14416
381 14416
382 14416
383 14416
384 14416
385 14416
386 14416
387 14416
388 14416
389 14416
390 14416
391 14416
392 14416
393 14416
394 14416
395 14416
396 14416
397 14416
398 14416
399 14416
400 14416
401 14416
402 14416
403 14416
404 14416
405 14416
406 14416
407 14416
408 14416
409 14416
410 14416
411 14416
412 14416
413 14416
414 14416
415 14416
416 14416
417 14416
418 14416
419 14416
420 14416
421 14416
422 14416
423 14416
424 14416
425 14416
426 14416
427 14416
428 14416
429 14416
430 14416
431 14416
432 14416
433 14416
434 14416
435 14416
436 14416
437 14416
438 14416
439 14416
440 14416
441 14416
442 14416
443 14416
444 14416
445 14416
446 14416
447 14416
448 14416
449 14416
450 14416
451 14416
452 14416
453 14416
454 14416
455 14416
456 14416
457 14416
458 14416
459 14416
460 14416
461 14416
462 14416
463 14416
464 14416
465 14416
466 14416
467 14416
468 14416
469 14416
470 14416
471 14416
472 14416
473 14416
474 14416
475 14416
476 14416
477 14416
478 14416
479 14416
480 14416
481 14416
482 14416
483 14416
484 14416
485 14416
486 14416
487 14416
488 14416
489 14416
490 14416
491 14416
492 14416
493 14416
494 14416
495 14416
496 14416
497 14416
498 14416
499 14416
500 14416
501 14416
502 14416
503 14416
504 14416
505 14416
506 14416
507 14416
508 14416
509 14416
510 14416
511 14416
512 14416
513 28752
514 28752
515 28752
516 28752
517 28752
518 28752
519 28752
520 28752
521 28752
522 28752
523 28752
524 28752
525 28752
526 28752
527 28752
528 28752
529 28752
530 28752
531 28752
532 28752
533 28752
534 28752
535 28752
536 28752
537 28752
538 28752
539 28752
540 28752
541 28752
542 28752
543 28752
544 28752
545 28752
546 28752
547 28752
548 28752
549 28752
550 28752
551 28752
552 28752
553 28752
554 28752
555 28752
556 28752
557 28752
558 28752
559 28752
560 28752
561 28752
562 28752
563 28752
564 28752
565 28752
566 28752
567 28752
568 28752
569 28752
570 28752
571 28752
572 28752
573 28752
574 28752
575 28752
576 28752
577 28752
578 28752
579 28752
580 28752
581 28752
582 28752
583 28752
584 28752
585 28752
586 28752
587 28752
588 28752
589 28752
590 28752
591 28752
592 28752
593 28752
594 28752
595 28752
596 28752
597 28752
598 28752
599 28752
600 28752
601 28752
602 28752
603 28752
604 28752
605 28752
606 28752
607 28752
608 28752
609 28752
610 28752
611 28752
612 28752
613 28752
614 28752
615 28752
616 28752
617 28752
618 28752
619 28752
620 28752
621 28752
622 28752
623 28752
624 28752
625 28752
626 28752
627 28752
628 28752
629 28752
630 28752
631 28752
632 28752
633 28752
634 28752
635 28752
636 28752
637 28752
638 28752
639 28752
640 28752
641 28752
642 28752
643 28752
644 28752
645 28752
646 28752
647 28752
648 28752
649 28752
650 28752
651 28752
652 28752
653 28752
654 28752
655 28752
656 28752
657 28752
658 28752
659 28752
660 28752
661 28752
662 28752
663 28752
664 28752
665 28752
666 28752
667 28752
668 28752
669 28752
670 28752
671 28752
672 28752
673 28752
674 28752
675 28752
676 28752
677 28752
678 28752
679 28752
680 28752
681 28752
682 28752
683 28752
684 28752
685 28752
686 28752
687 28752
688 28752
689 28752
690 28752
691 28752
692 28752
693 28752
694 28752
695 28752
696 28752
697 28752
698 28752
699 28752
700 28752
701 28752
702 28752
703 28752
704 28752
705 28752
706 28752
707 28752
708 28752
709 28752
710 28752
711 28752
712 28752
713 28752
714 28752
715 28752
716 28752
717 28752
718 28752
719 28752
720 28752
721 28752
722 28752
723 28752
724 28752
725 28752
726 28752
727 28752
728 28752
729 28752
730 28752
731 28752
732 28752
733 28752
734 28752
735 28752
736 28752
737 28752
738 28752
739 28752
740 28752
741 28752
742 28752
743 28752
744 28752
745 28752
746 28752
747 28752
748 28752
749 28752
750 28752
751 28752
752 28752
753 28752
754 28752
755 28752
756 28752
757 28752
758 28752
759 28752
760 28752
761 28752
762 28752
763 28752
764 28752
765 28752
766 28752
767 28752
768 28752
769 28752
770 28752
771 28752
772 28752
773 28752
774 28752
775 28752
776 28752
777 28752
778 28752
779 28752
780 28752
781 28752
782 28752
783 28752
784 28752
785 28752
786 28752
787 28752
788 28752
789 28752
790 28752
791 28752
792 28752
793 28752
794 28752
795 28752
796 28752
797 28752
798 28752
799 28752
800 28752
801 28752
802 28752
803 28752
804 28752
805 28752
806 28752
807 28752
808 28752
809 28752
810 28752
811 28752
812 28752
813 28752
814 28752
815 28752
816 28752
817 28752
818 28752
819 28752
820 28752
821 28752
822 28752
823 28752
824 28752
825 28752
826 28752
827 28752
828 28752
829 28752
830 28752
831 28752
832 28752
833 28752
834 28752
835 28752
836 28752
837 28752
838 28752
839 28752
840 28752
841 28752
842 28752
843 28752
844 28752
845 28752
846 28752
847 28752
848 28752
849 28752
850 28752
851 28752
852 28752
853 28752
854 28752
855 28752
856 28752
857 28752
858 28752
859 28752
860 28752
861 28752
862 28752
863 28752
864 28752
865 28752
866 28752
867 28752
868 28752
869 28752
870 28752
871 28752
872 28752
873 28752
874 28752
875 28752
876 28752
877 28752
878 28752
879 28752
880 28752
881 28752
882 28752
883 28752
884 28752
885 28752
886 28752
887 28752
888 28752
889 28752
890 28752
891 28752
892 28752
893 28752
894 28752
895 28752
896 28752
897 28752
898 28752
899 28752
900 28752
901 28752
902 28752
903 28752
904 28752
905 28752
906 28752
907 28752
908 28752
909 28752
910 28752
911 28752
912 28752
913 28752
914 28752
915 28752
916 28752
917 28752
918 28752
919 28752
920 28752
921 28752
922 28752
923 28752
924 28752
925 28752
926 28752
927 28752
928 28752
929 28752
930 28752
931 28752
932 28752
933 28752
934 28752
935 28752
936 28752
937 28752
938 28752
939 28752
940 28752
941 28752
942 28752
943 28752
944 28752
945 28752
946 28752
947 28752
948 28752
949 28752
950 28752
951 28752
952 28752
953 28752
954 28752
955 28752
956 28752
957 28752
958 28752
959 28752
960 28752
961 28752
962 28752
963 28752
964 28752
965 28752
966 28752
967 28752
968 28752
969 28752
970 28752
971 28752
972 28752
973 28752
974 28752
975 28752
976 28752
977 28752
978 28752
979 28752
980 28752
981 28752
982 28752
983 28752
984 28752
985 28752
986 28752
987 28752
988 28752
989 28752
990 28752
991 28752
992 28752
993 28752
994 28752
995 28752
996 28752
997 28752
998 28752
999 28752
1000 28736
2000 57408
3000 114752
4000 114752
5000 229440
6000 229440
7000 229440
8000 229440
9000 458816
10000 458816
11000 458816
12000 458816
13000 458816
14000 458816
15000 458816
16000 458816
17000 917568
18000 917568
19000 917568
20000 917568
21000 917568
22000 917568
23000 917568
24000 917568
25000 917568
26000 917568
27000 917568
28000 917568
29000 917568
30000 917568
31000 917568
32000 917568
33000 2097216
34000 2097216
35000 2097216
36000 2097216
37000 2097216
38000 2097216
39000 2097216
40000 2097216
0 16
1 80
2 80
3 80
4 80
5 144
6 144
7 144
8 144
9 272
10 272
11 272
12 272
13 272
14 272
15 272
16 272
17 528
18 528
19 528
20 528
21 528
22 528
23 528
24 528
25 528
26 528
27 528
28 528
29 528
30 528
31 528
32 528
33 1040
34 1040
35 1040
36 1040
37 1040
38 1040
39 1040
40 1040
41 1040
42 1040
43 1040
44 1040
45 1040
46 1040
47 1040
48 1040
49 1040
50 1040
51 1040
52 1040
53 1040
54 1040
55 1040
56 1040
57 1040
58 1040
59 1040
60 1040
61 1040
62 1040
63 1040
64 1040
65 2064
66 2064
67 2064
68 2064
69 2064
70 2064
71 2064
72 2064
73 2064
74 2064
75 2064
76 2064
77 2064
78 2064
79 2064
80 2064
81 2064
82 2064
83 2064
84 2064
85 2064
86 2064
87 2064
88 2064
89 2064
90 2064
91 2064
92 2064
93 2064
94 2064
95 2064
96 2064
97 2064
98 2064
99 2064
100 2064
101 2064
102 2064
103 2064
104 2064
105 2064
106 2064
107 2064
108 2064
109 2064
110 2064
111 2064
112 2064
113 2064
114 2064
115 2064
116 2064
117 2064
118 2064
119 2064
120 2064
121 2064
122 2064
123 2064
124 2064
125 2064
126 2064
127 2064
128 2064
129 4112
130 4112
131 4112
132 4112
133 4112
134 4112
135 4112
136 4112
137 4112
138 4112
139 4112
140 4112
141 4112
142 4112
143 4112
144 4112
145 4112
146 4112
147 4112
148 4112
149 4112
150 4112
151 4112
152 4112
153 4112
154 4112
155 4112
156 4112
157 4112
158 4112
159 4112
160 4112
161 4112
162 4112
163 4112
164 4112
165 4112
166 4112
167 4112
168 4112
169 4112
170 4112
171 4112
172 4112
173 4112
174 4112
175 4112
176 4112
177 4112
178 4112
179 4112
180 4112
181 4112
182 4112
183 4112
184 4112
185 4112
186 4112
187 4112
188 4112
189 4112
190 4112
191 4112
192 4112
193 4112
194 4112
195 4112
196 4112
197 4112
198 4112
199 4112
200 4112
201 4112
202 4112
203 4112
204 4112
205 4112
206 4112
207 4112
208 4112
209 4112
210 4112
211 4112
212 4112
213 4112
214 4112
215 4112
216 4112
217 4112
218 4112
219 4112
220 4112
221 4112
222 4112
223 4112
224 4112
225 4112
226 4112
227 4112
228 4112
229 4112
230 4112
231 4112
232 4112
233 4112
234 4112
235 4112
236 4112
237 4112
238 4112
239 4112
240 4112
241 4112
242 4112
243 4112
244 4112
245 4112
246 4112
247 4112
248 4112
249 4112
250 4112
251 4112
252 4112
253 4112
254 4112
255 4112
256 4112
257 8208
258 8208
259 8208
260 8208
261 8208
262 8208
263 8208
264 8208
265 8208
266 8208
267 8208
268 8208
269 8208
270 8208
271 8208
272 8208
273 8208
274 8208
275 8208
276 8208
277 8208
278 8208
279 8208
280 8208
281 8208
282 8208
283 8208
284 8208
285 8208
286 8208
287 8208
288 8208
289 8208
290 8208
291 8208
292 8208
293 8208
294 8208
295 8208
296 8208
297 8208
298 8208
299 8208
300 8208
301 8208
302 8208
303 8208
304 8208
305 8208
306 8208
307 8208
308 8208
309 8208
310 8208
311 8208
312 8208
313 8208
314 8208
315 8208
316 8208
317 8208
318 8208
319 8208
320 8208
321 8208
322 8208
323 8208
324 8208
325 8208
326 8208
327 8208
328 8208
329 8208
330 8208
331 8208
332 8208
333 8208
334 8208
335 8208
336 8208
337 8208
338 8208
339 8208
340 8208
341 8208
342 8208
343 8208
344 8208
345 8208
346 8208
347 8208
348 8208
349 8208
350 8208
351 8208
352 8208
353 8208
354 8208
355 8208
356 8208
357 8208
358 8208
359 8208
360 8208
361 8208
362 8208
363 8208
364 8208
365 8208
366 8208
367 8208
368 8208
369 8208
370 8208
371 8208
372 8208
373 8208
374 8208
375 8208
376 8208
377 8208
378 8208
379 8208
380 8208
381 8208
382 8208
383 8208
384 8208
385 8208
386 8208
387 8208
388 8208
389 8208
390 8208
391 8208
392 8208
393 8208
394 8208
395 8208
396 8208
397 8208
398 8208
399 8208
400 8208
401 8208
402 8208
403 8208
404 8208
405 8208
406 8208
407 8208
408 8208
409 8208
410 8208
411 8208
412 8208
413 8208
414 8208
415 8208
416 8208
417 8208
418 8208
419 8208
420 8208
421 8208
422 8208
423 8208
424 8208
425 8208
426 8208
427 8208
428 8208
429 8208
430 8208
431 8208
432 8208
433 8208
434 8208
435 8208
436 8208
437 8208
438 8208
439 8208
440 8208
441 8208
442 8208
443 8208
444 8208
445 8208
446 8208
447 8208
448 8208
449 8208
450 8208
451 8208
452 8208
453 8208
454 8208
455 8208
456 8208
457 8208
458 8208
459 8208
460 8208
461 8208
462 8208
463 8208
464 8208
465 8208
466 8208
467 8208
468 8208
469 8208
470 8208
471 8208
472 8208
473 8208
474 8208
475 8208
476 8208
477 8208
478 8208
479 8208
480 8208
481 8208
482 8208
483 8208
484 8208
485 8208
486 8208
487 8208
488 8208
489 8208
490 8208
491 8208
492 8208
493 8208
494 8208
495 8208
496 8208
497 8208
498 8208
499 8208
500 8208
501 8208
502 8208
503 8208
504 8208
505 8208
506 8208
507 8208
508 8208
509 8208
510 8208
511 8208
512 8208
513 16400
514 16400
515 16400
516 16400
517 16400
518 16400
519 16400
520 16400
521 16400
522 16400
523 16400
524 16400
525 16400
526 16400
527 16400
528 16400
529 16400
530 16400
531 16400
532 16400
533 16400
534 16400
535 16400
536 16400
537 16400
538 16400
539 16400
540 16400
541 16400
542 16400
543 16400
544 16400
545 16400
546 16400
547 16400
548 16400
549 16400
550 16400
551 16400
552 16400
553 16400
554 16400
555 16400
556 16400
557 16400
558 16400
559 16400
560 16400
561 16400
562 16400
563 16400
564 16400
565 16400
566 16400
567 16400
568 16400
569 16400
570 16400
571 16400
572 16400
573 16400
574 16400
575 16400
576 16400
577 16400
578 16400
579 16400
580 16400
581 16400
582 16400
583 16400
584 16400
585 16400
586 16400
587 16400
588 16400
589 16400
590 16400
591 16400
592 16400
593 16400
594 16400
595 16400
596 16400
597 16400
598 16400
599 16400
600 16400
601 16400
602 16400
603 16400
604 16400
605 16400
606 16400
607 16400
608 16400
609 16400
610 16400
611 16400
612 16400
613 16400
614 16400
615 16400
616 16400
617 16400
618 16400
619 16400
620 16400
621 16400
622 16400
623 16400
624 16400
625 16400
626 16400
627 16400
628 16400
629 16400
630 16400
631 16400
632 16400
633 16400
634 16400
635 16400
636 16400
637 16400
638 16400
639 16400
640 16400
641 16400
642 16400
643 16400
644 16400
645 16400
646 16400
647 16400
648 16400
649 16400
650 16400
651 16400
652 16400
653 16400
654 16400
655 16400
656 16400
657 16400
658 16400
659 16400
660 16400
661 16400
662 16400
663 16400
664 16400
665 16400
666 16400
667 16400
668 16400
669 16400
670 16400
671 16400
672 16400
673 16400
674 16400
675 16400
676 16400
677 16400
678 16400
679 16400
680 16400
681 16400
682 16400
683 16400
684 16400
685 16400
686 16400
687 16400
688 16400
689 16400
690 16400
691 16400
692 16400
693 16400
694 16400
695 16400
696 16400
697 16400
698 16400
699 16400
700 16400
701 16400
702 16400
703 16400
704 16400
705 16400
706 16400
707 16400
708 16400
709 16400
710 16400
711 16400
712 16400
713 16400
714 16400
715 16400
716 16400
717 16400
718 16400
719 16400
720 16400
721 16400
722 16400
723 16400
724 16400
725 16400
726 16400
727 16400
728 16400
729 16400
730 16400
731 16400
732 16400
733 16400
734 16400
735 16400
736 16400
737 16400
738 16400
739 16400
740 16400
741 16400
742 16400
743 16400
744 16400
745 16400
746 16400
747 16400
748 16400
749 16400
750 16400
751 16400
752 16400
753 16400
754 16400
755 16400
756 16400
757 16400
758 16400
759 16400
760 16400
761 16400
762 16400
763 16400
764 16400
765 16400
766 16400
767 16400
768 16400
769 16400
770 16400
771 16400
772 16400
773 16400
774 16400
775 16400
776 16400
777 16400
778 16400
779 16400
780 16400
781 16400
782 16400
783 16400
784 16400
785 16400
786 16400
787 16400
788 16400
789 16400
790 16400
791 16400
792 16400
793 16400
794 16400
795 16400
796 16400
797 16400
798 16400
799 16400
800 16400
801 16400
802 16400
803 16400
804 16400
805 16400
806 16400
807 16400
808 16400
809 16400
810 16400
811 16400
812 16400
813 16400
814 16400
815 16400
816 16400
817 16400
818 16400
819 16400
820 16400
821 16400
822 16400
823 16400
824 16400
825 16400
826 16400
827 16400
828 16400
829 16400
830 16400
831 16400
832 16400
833 16400
834 16400
835 16400
836 16400
837 16400
838 16400
839 16400
840 16400
841 16400
842 16400
843 16400
844 16400
845 16400
846 16400
847 16400
848 16400
849 16400
850 16400
851 16400
852 16400
853 16400
854 16400
855 16400
856 16400
857 16400
858 16400
859 16400
860 16400
861 16400
862 16400
863 16400
864 16400
865 16400
866 16400
867 16400
868 16400
869 16400
870 16400
871 16400
872 16400
873 16400
874 16400
875 16400
876 16400
877 16400
878 16400
879 16400
880 16400
881 16400
882 16400
883 16400
884 16400
885 16400
886 16400
887 16400
888 16400
889 16400
890 16400
891 16400
892 16400
893 16400
894 16400
895 16400
896 16400
897 16400
898 16400
899 16400
900 16400
901 16400
902 16400
903 16400
904 16400
905 16400
906 16400
907 16400
908 16400
909 16400
910 16400
911 16400
912 16400
913 16400
914 16400
915 16400
916 16400
917 16400
918 16400
919 16400
920 16400
921 16400
922 16400
923 16400
924 16400
925 16400
926 16400
927 16400
928 16400
929 16400
930 16400
931 16400
932 16400
933 16400
934 16400
935 16400
936 16400
937 16400
938 16400
939 16400
940 16400
941 16400
942 16400
943 16400
944 16400
945 16400
946 16400
947 16400
948 16400
949 16400
950 16400
951 16400
952 16400
953 16400
954 16400
955 16400
956 16400
957 16400
958 16400
959 16400
960 16400
961 16400
962 16400
963 16400
964 16400
965 16400
966 16400
967 16400
968 16400
969 16400
970 16400
971 16400
972 16400
973 16400
974 16400
975 16400
976 16400
977 16400
978 16400
979 16400
980 16400
981 16400
982 16400
983 16400
984 16400
985 16400
986 16400
987 16400
988 16400
989 16400
990 16400
991 16400
992 16400
993 16400
994 16400
995 16400
996 16400
997 16400
998 16400
999 16400
1000 28736
2000 57408
3000 114752
4000 114752
5000 229440
6000 229440
7000 229440
8000 229440
9000 458816
10000 458816
11000 458816
12000 458816
13000 458816
14000 458816
15000 458816
16000 458816
17000 917568
18000 917568
19000 917568
20000 917568
21000 917568
22000 917568
23000 917568
24000 917568
25000 917568
26000 917568
27000 917568
28000 917568
29000 917568
30000 917568
31000 917568
32000 917568
33000 2097216
34000 2097216
35000 2097216
36000 2097216
37000 2097216
38000 2097216
39000 2097216
40000 2097216
0 16
1 64
2 64
3 64
4 64
5 112
6 112
7 112
8 112
9 208
10 208
11 208
12 208
13 208
14 208
15 208
16 208
17 400
18 400
19 400
20 400
21 400
22 400
23 400
24 400
25 400
26 400
27 400
28 400
29 400
30 400
31 400
32 400
33 784
34 784
35 784
36 784
37 784
38 784
39 784
40 784
41 784
42 784
43 784
44 784
45 784
46 784
47 784
48 784
49 784
50 784
51 784
52 784
53 784
54 784
55 784
56 784
57 784
58 784
59 784
60 784
61 784
62 784
63 784
64 784
65 1552
66 1552
67 1552
68 1552
69 1552
70 1552
71 1552
72 1552
73 1552
74 1552
75 1552
76 1552
77 1552
78 1552
79 1552
80 1552
81 1552
82 1552
83 1552
84 1552
85 1552
86 1552
87 1552
88 1552
89 1552
90 1552
91 1552
92 1552
93 1552
94 1552
95 1552
96 1552
97 1552
98 1552
99 1552
100 1552
101 1552
102 1552
103 1552
104 1552
105 1552
106 1552
107 1552
108 1552
109 1552
110 1552
111 1552
112 1552
113 1552
114 1552
115 1552
116 1552
117 1552
118 1552
119 1552
120 1552
121 1552
122 1552
123 1552
124 1552
125 1552
126 1552
127 1552
128 1552
129 3088
130 3088
131 3088
132 3088
133 3088
134 3088
135 3088
136 3088
137 3088
138 3088
139 3088
140 3088
141 3088
142 3088
143 3088
144 3088
145 3088
146 3088
147 3088
148 3088
149 3088
150 3088
151 3088
152 3088
153 3088
154 3088
155 3088
156 3088
157 3088
158 3088
159 3088
160 3088
161 3088
162 3088
163 3088
164 3088
165 3088
166 3088
167 3088
168 3088
169 3088
170 3088
171 3088
172 3088
173 3088
174 3088
175 3088
176 3088
177 3088
178 3088
179 3088
180 3088
181 3088
182 3088
183 3088
184 3088
185 3088
186 3088
187 3088
188 3088
189 3088
190 3088
191 3088
192 3088
193 3088
194 3088
195 3088
196 3088
197 3088
198 3088
199 3088
200 3088
201 3088
202 3088
203 3088
204 3088
205 3088
206 3088
207 3088
208 3088
209 3088
210 3088
211 3088
212 3088
213 3088
214 3088
215 3088
216 3088
217 3088
218 3088
219 3088
220 3088
221 3088
222 3088
223 3088
224 3088
225 3088
226 3088
227 3088
228 3088
229 3088
230 3088
231 3088
232 3088
233 3088
234 3088
235 3088
236 3088
237 3088
238 3088
239 3088
240 3088
241 3088
242 3088
243 3088
244 3088
245 3088
246 3088
247 3088
248 3088
249 3088
250 3088
251 3088
252 3088
253 3088
254 3088
255 3088
256 3088
257 6160
258 6160
259 6160
260 6160
261 6160
262 6160
263 6160
264 6160
265 6160
266 6160
267 6160
268 6160
269 6160
270 6160
271 6160
272 6160
273 6160
274 6160
275 6160
276 6160
277 6160
278 6160
279 6160
280 6160
281 6160
282 6160
283 6160
284 6160
285 6160
286 6160
287 6160
288 6160
289 6160
290 6160
291 6160
292 6160
293 6160
294 6160
295 6160
296 6160
297 6160
298 6160
299 6160
300 6160
301 6160
302 6160
303 6160
304 6160
305 6160
306 6160
307 6160
308 6160
309 6160
310 6160
311 6160
312 6160
313 6160
314 6160
315 6160
316 6160
317 6160
318 6160
319 6160
320 6160
321 6160
322 6160
323 6160
324 6160
325 6160
326 6160
327 6160
328 6160
329 6160
330 6160
331 6160
332 6160
333 6160
334 6160
335 6160
336 6160
337 6160
338 6160
339 6160
340 6160
341 6160
342 6160
343 6160
344 6160
345 6160
346 6160
347 6160
348 6160
349 6160
350 6160
351 6160
352 6160
353 6160
354 6160
355 6160
356 6160
357 6160
358 6160
359 6160
360 6160
361 6160
362 6160
363 6160
364 6160
365 6160
366 6160
367 6160
368 6160
369 6160
370 6160
371 6160
372 6160
373 6160
374 6160
375 6160
376 6160
377 6160
378 6160
379 6160
380 6160
381 6160
382 6160
383 6160
384 6160
385 6160
386 6160
387 6160
388 6160
389 6160
390 6160
391 6160
392 6160
393 6160
394 6160
395 6160
396 6160
397 6160
398 6160
399 6160
400 6160
401 6160
402 6160
403 6160
404 6160
405 6160
406 6160
407 6160
408 6160
409 6160
410 6160
411 6160
412 6160
413 6160
414 6160
415 6160
416 6160
417 6160
418 6160
419 6160
420 6160
421 6160
422 6160
423 6160
424 6160
425 6160
426 6160
427 6160
428 6160
429 6160
430 6160
431 6160
432 6160
433 6160
434 6160
435 6160
436 6160
437 6160
438 6160
439 6160
440 6160
441 6160
442 6160
443 6160
444 6160
445 6160
446 6160
447 6160
448 6160
449 6160
450 6160
451 6160
452 6160
453 6160
454 6160
455 6160
456 6160
457 6160
458 6160
459 6160
460 6160
461 6160
462 6160
463 6160
464 6160
465 6160
466 6160
467 6160
468 6160
469 6160
470 6160
471 6160
472 6160
473 6160
474 6160
475 6160
476 6160
477 6160
478 6160
479 6160
480 6160
481 6160
482 6160
483 6160
484 6160
485 6160
486 6160
487 6160
488 6160
489 6160
490 6160
491 6160
492 6160
493 6160
494 6160
495 6160
496 6160
497 6160
498 6160
499 6160
500 6160
501 6160
502 6160
503 6160
504 6160
505 6160
506 6160
507 6160
508 6160
509 6160
510 6160
511 6160
512 6160
513 12304
514 12304
515 12304
516 12304
517 12304
518 12304
519 12304
520 12304
521 12304
522 12304
523 12304
524 12304
525 12304
526 12304
527 12304
528 12304
529 12304
530 12304
531 12304
532 12304
533 12304
534 12304
535 12304
536 12304
537 12304
538 12304
539 12304
540 12304
541 12304
542 12304
543 12304
544 12304
545 12304
546 12304
547 12304
548 12304
549 12304
550 12304
551 12304
552 12304
553 12304
554 12304
555 12304
556 12304
557 12304
558 12304
559 12304
560 12304
561 12304
562 12304
563 12304
564 12304
565 12304
566 12304
567 12304
568 12304
569 12304
570 12304
571 12304
572 12304
573 12304
574 12304
575 12304
576 12304
577 12304
578 12304
579 12304
580 12304
581 12304
582 12304
583 12304
584 12304
585 12304
586 12304
587 12304
588 12304
589 12304
590 12304
591 12304
592 12304
593 12304
594 12304
595 12304
596 12304
597 12304
598 12304
599 12304
600 12304
601 12304
602 12304
603 12304
604 12304
605 12304
606 12304
607 12304
608 12304
609 12304
610 12304
611 12304
612 12304
613 12304
614 12304
615 12304
616 12304
617 12304
618 12304
619 12304
620 12304
621 12304
622 12304
623 12304
624 12304
625 12304
626 12304
627 12304
628 12304
629 12304
630 12304
631 12304
632 12304
633 12304
634 12304
635 12304
636 12304
637 12304
638 12304
639 12304
640 12304
641 12304
642 12304
643 12304
644 12304
645 12304
646 12304
647 12304
648 12304
649 12304
650 12304
651 12304
652 12304
653 12304
654 12304
655 12304
656 12304
657 12304
658 12304
659 12304
660 12304
661 12304
662 12304
663 12304
664 12304
665 12304
666 12304
667 12304
668 12304
669 12304
670 12304
671 12304
672 12304
673 12304
674 12304
675 12304
676 12304
677 12304
678 12304
679 12304
680 12304
681 12304
682 12304
683 12304
684 12304
685 12304
686 12304
687 12304
688 12304
689 12304
690 12304
691 12304
692 12304
693 12304
694 12304
695 12304
696 12304
697 12304
698 12304
699 12304
700 12304
701 12304
702 12304
703 12304
704 12304
705 12304
706 12304
707 12304
708 12304
709 12304
710 12304
711 12304
712 12304
713 12304
714 12304
715 12304
716 12304
717 12304
718 12304
719 12304
720 12304
721 12304
722 12304
723 12304
724 12304
725 12304
726 12304
727 12304
728 12304
729 12304
730 12304
731 12304
732 12304
733 12304
734 12304
735 12304
736 12304
737 12304
738 12304
739 12304
740 12304
741 12304
742 12304
743 12304
744 12304
745 12304
746 12304
747 12304
748 12304
749 12304
750 12304
751 12304
752 12304
753 12304
754 12304
755 12304
756 12304
757 12304
758 12304
759 12304
760 12304
761 12304
762 12304
763 12304
764 12304
765 12304
766 12304
767 12304
768 12304
769 12304
770 12304
771 12304
772 12304
773 12304
774 12304
775 12304
776 12304
777 12304
778 12304
779 12304
780 12304
781 12304
782 12304
783 12304
784 12304
785 12304
786 12304
787 12304
788 12304
789 12304
790 12304
791 12304
792 12304
793 12304
794 12304
795 12304
796 12304
797 12304
798 12304
799 12304
800 12304
801 12304
802 12304
803 12304
804 12304
805 12304
806 12304
807 12304
808 12304
809 12304
810 12304
811 12304
812 12304
813 12304
814 12304
815 12304
816 12304
817 12304
818 12304
819 12304
820 12304
821 12304
822 12304
823 12304
824 12304
825 12304
826 12304
827 12304
828 12304
829 12304
830 12304
831 12304
832 12304
833 12304
834 12304
835 12304
836 12304
837 12304
838 12304
839 12304
840 12304
841 12304
842 12304
843 12304
844 12304
845 12304
846 12304
847 12304
848 12304
849 12304
850 12304
851 12304
852 12304
853 12304
854 12304
855 12304
856 12304
857 12304
858 12304
859 12304
860 12304
861 12304
862 12304
863 12304
864 12304
865 12304
866 12304
867 12304
868 12304
869 12304
870 12304
871 12304
872 12304
873 12304
874 12304
875 12304
876 12304
877 12304
878 12304
879 12304
880 12304
881 12304
882 12304
883 12304
884 12304
885 12304
886 12304
887 12304
888 12304
889 12304
890 12304
891 12304
892 12304
893 12304
894 12304
895 12304
896 12304
897 12304
898 12304
899 12304
900 12304
901 12304
902 12304
903 12304
904 12304
905 12304
906 12304
907 12304
908 12304
909 12304
910 12304
911 12304
912 12304
913 12304
914 12304
915 12304
916 12304
917 12304
918 12304
919 12304
920 12304
921 12304
922 12304
923 12304
924 12304
925 12304
926 12304
927 12304
928 12304
929 12304
930 12304
931 12304
932 12304
933 12304
934 12304
935 12304
936 12304
937 12304
938 12304
939 12304
940 12304
941 12304
942 12304
943 12304
944 12304
945 12304
946 12304
947 12304
948 12304
949 12304
950 12304
951 12304
952 12304
953 12304
954 12304
955 12304
956 12304
957 12304
958 12304
959 12304
960 12304
961 12304
962 12304
963 12304
964 12304
965 12304
966 12304
967 12304
968 12304
969 12304
970 12304
971 12304
972 12304
973 12304
974 12304
975 12304
976 12304
977 12304
978 12304
979 12304
980 12304
981 12304
982 12304
983 12304
984 12304
985 12304
986 12304
987 12304
988 12304
989 12304
990 12304
991 12304
992 12304
993 12304
994 12304
995 12304
996 12304
997 12304
998 12304
999 12304
1000 28736
2000 57408
3000 114752
4000 114752
5000 229440
6000 229440
7000 229440
8000 229440
9000 458816
10000 458816
11000 458816
12000 458816
13000 458816
14000 458816
15000 458816
16000 458816
17000 917568
18000 917568
19000 917568
20000 917568
21000 917568
22000 917568
23000 917568
24000 917568
25000 917568
26000 917568
27000 917568
28000 917568
29000 917568
30000 917568
31000 917568
32000 917568
33000 2097216
34000 2097216
35000 2097216
36000 2097216
37000 2097216
38000 2097216
39000 2097216
40000 2097216
1 64
2 64
3 64
4 64
5 112
6 112
7 112
8 112
9 208
10 208
11 208
12 208
13 208
14 208
15 208
16 208
17 400
18 400
19 400
20 400
21 400
22 400
23 400
24 400
25 400
26 400
27 400
28 400
29 400
30 400
31 400
32 400
33 784
34 784
35 784
36 784
37 784
38 784
39 784
40 784
41 784
42 784
43 784
44 784
45 784
46 784
47 784
48 784
49 784
50 784
51 784
52 784
53 784
54 784
55 784
56 784
57 784
58 784
59 784
60 784
61 784
62 784
63 784
64 784
65 1552
66 1552
67 1552
68 1552
69 1552
70 1552
71 1552
72 1552
73 1552
74 1552
75 1552
76 1552
77 1552
78 1552
79 1552
80 1552
81 1552
82 1552
83 1552
84 1552
85 1552
86 1552
87 1552
88 1552
89 1552
90 1552
91 1552
92 1552
93 1552
94 1552
95 1552
96 1552
97 1552
98 1552
99 1552
100 1552
101 1552
102 1552
103 1552
104 1552
105 1552
106 1552
107 1552
108 1552
109 1552
110 1552
111 1552
112 1552
113 1552
114 1552
115 1552
116 1552
117 1552
118 1552
119 1552
120 1552
121 1552
122 1552
123 1552
124 1552
125 1552
126 1552
127 1552
128 1552
129 3088
130 3088
131 3088
132 3088
133 3088
134 3088
135 3088
136 3088
137 3088
138 3088
139 3088
140 3088
141 3088
142 3088
143 3088
144 3088
145 3088
146 3088
147 3088
148 3088
149 3088
150 3088
151 3088
152 3088
153 3088
154 3088
155 3088
156 3088
157 3088
158 3088
159 3088
160 3088
161 3088
162 3088
163 3088
164 3088
165 3088
166 3088
167 3088
168 3088
169 3088
170 3088
171 3088
172 3088
173 3088
174 3088
175 3088
176 3088
177 3088
178 3088
179 3088
180 3088
181 3088
182 3088
183 3088
184 3088
185 3088
186 3088
187 3088
188 3088
189 3088
190 3088
191 3088
192 3088
193 3088
194 3088
195 3088
196 3088
197 3088
198 3088
199 3088
200 3088
201 3088
202 3088
203 3088
204 3088
205 3088
206 3088
207 3088
208 3088
209 3088
210 3088
211 3088
212 3088
213 3088
214 3088
215 3088
216 3088
217 3088
218 3088
219 3088
220 3088
221 3088
222 3088
223 3088
224 3088
225 3088
226 3088
227 3088
228 3088
229 3088
230 3088
231 3088
232 3088
233 3088
234 3088
235 3088
236 3088
237 3088
238 3088
239 3088
240 3088
241 3088
242 3088
243 3088
244 3088
245 3088
246 3088
247 3088
248 3088
249 3088
250 3088
251 3088
252 3088
253 3088
254 3088
255 3088
256 3088
257 6160
258 6160
259 6160
260 6160
261 6160
262 6160
263 6160
264 6160
265 6160
266 6160
267 6160
268 6160
269 6160
270 6160
271 6160
272 6160
273 6160
274 6160
275 6160
276 6160
277 6160
278 6160
279 6160
280 6160
281 6160
282 6160
283 6160
284 6160
285 6160
286 6160
287 6160
288 6160
289 6160
290 6160
291 6160
292 6160
293 6160
294 6160
295 6160
296 6160
297 6160
298 6160
299 6160
300 6160
301 6160
302 6160
303 6160
304 6160
305 6160
306 6160
307 6160
308 6160
309 6160
310 6160
311 6160
312 6160
313 6160
314 6160
315 6160
316 6160
317 6160
318 6160
319 6160
320 6160
321 6160
322 6160
323 6160
324 6160
325 6160
326 6160
327 6160
328 6160
329 6160
330 6160
331 6160
332 6160
333 6160
334 6160
335 6160
336 6160
337 6160
338 6160
339 6160
340 6160
341 6160
342 6160
343 6160
344 6160
345 6160
346 6160
347 6160
348 6160
349 6160
350 6160
351 6160
352 6160
353 6160
354 6160
355 6160
356 6160
357 6160
358 6160
359 6160
360 6160
361 6160
362 6160
363 6160
364 6160
365 6160
366 6160
367 6160
368 6160
369 6160
370 6160
371 6160
372 6160
373 6160
374 6160
375 6160
376 6160
377 6160
378 6160
379 6160
380 6160
381 6160
382 6160
383 6160
384 6160
385 6160
386 6160
387 6160
388 6160
389 6160
390 6160
391 6160
392 6160
393 6160
394 6160
395 6160
396 6160
397 6160
398 6160
399 6160
400 6160
401 6160
402 6160
403 6160
404 6160
405 6160
406 6160
407 6160
408 6160
409 6160
410 6160
411 6160
412 6160
413 6160
414 6160
415 6160
416 6160
417 6160
418 6160
419 6160
420 6160
421 6160
422 6160
423 6160
424 6160
425 6160
426 6160
427 6160
428 6160
429 6160
430 6160
431 6160
432 6160
433 6160
434 6160
435 6160
436 6160
437 6160
438 6160
439 6160
440 6160
441 6160
442 6160
443 6160
444 6160
445 6160
446 6160
447 6160
448 6160
449 6160
450 6160
451 6160
452 6160
453 6160
454 6160
455 6160
456 6160
457 6160
458 6160
459 6160
460 6160
461 6160
462 6160
463 6160
464 6160
465 6160
466 6160
467 6160
468 6160
469 6160
470 6160
471 6160
472 6160
473 6160
474 6160
475 6160
476 6160
477 6160
478 6160
479 6160
480 6160
481 6160
482 6160
483 6160
484 6160
485 6160
486 6160
487 6160
488 6160
489 6160
490 6160
491 6160
492 6160
493 6160
494 6160
495 6160
496 6160
497 6160
498 6160
499 6160
500 6160
501 6160
502 6160
503 6160
504 6160
505 6160
506 6160
507 6160
508 6160
509 6160
510 6160
511 6160
512 6160
513 12304
514 12304
515 12304
516 12304
517 12304
518 12304
519 12304
520 12304
521<