summaryrefslogtreecommitdiffhomepage
AgeCommit message (Collapse)Author
2020-11-10Reduce memory usage of Hash objectKOBAYASHI Shuji
## Implementation Summary * Change entry list from segmented list to flat array. * Change value of hash bucket from pointer to entry to index of entry list, and represent it by variable length bits according to capacity of hash buckets. * Store management information about entry list and hash table to `struct RHash` as much as possible. ## Benchmark Summary Only the results of typical situations on 64-bit Word-boxing are present here. For more detailed information, including consideration, see below (although most of the body is written in Japanese). * https://shuujii.github.io/mruby-hash-benchmark ### Memory Usage Lower value is better. | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 344B | 256B | 0.74419x | | 40 | 1,464B | 840B | 0.57377x | | 200 | 8,056B | 3,784B | 0.46971x | | 500 | 17,169B | 9,944B | 0.57949x | ### Performance Higher value is better. #### `mrb_hash_set` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 1.41847M i/s | 1.36004M i/s | 0.95881x | | 40 | 0.39224M i/s | 0.31888M i/s | 0.81296x | | 200 | 0.03780M i/s | 0.04290M i/s | 1.13494x | | 500 | 0.01225M i/s | 0.01314M i/s | 1.07275x | #### `mrb_hash_get` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 26.05920M i/s | 30.19543M i/s | 1.15872x | | 40 | 44.26420M i/s | 32.75781M i/s | 0.74005x | | 200 | 44.55171M i/s | 31.56926M i/s | 0.70860x | | 500 | 39.19250M i/s | 29.73806M i/s | 0.75877x | #### `mrb_hash_each` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 25.11964M i/s | 30.34167M i/s | 1.20789x | | 40 | 11.74253M i/s | 13.25539M i/s | 1.12884x | | 200 | 2.01133M i/s | 2.97214M i/s | 1.47770x | | 500 | 0.87411M i/s | 1.21178M i/s | 1.38631x | #### `Hash#[]=` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 0.50095M i/s | 0.56490M i/s | 1.12764x | | 40 | 0.19132M i/s | 0.18392M i/s | 0.96129x | | 200 | 0.03624M i/s | 0.03256M i/s | 0.89860x | | 500 | 0.01527M i/s | 0.01236M i/s | 0.80935x | #### `Hash#[]` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 11.53211M i/s | 12.78806M i/s | 1.10891x | | 40 | 15.26920M i/s | 13.37529M i/s | 0.87596x | | 200 | 15.28550M i/s | 13.36410M i/s | 0.87430x | | 500 | 14.57695M i/s | 12.75388M i/s | 0.87494x | #### `Hash#each` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 0.30462M i/s | 0.27080M i/s | 0.88898x | | 40 | 0.12912M i/s | 0.11704M i/s | 0.90642x | | 200 | 0.02638M i/s | 0.02402M i/s | 0.91071x | | 500 | 0.01066M i/s | 0.00959M i/s | 0.89953x | #### `Hash#delete` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 7.84167M i/s | 6.96419M i/s | 0.88810x | | 40 | 6.91292M i/s | 7.41427M i/s | 1.07252x | | 200 | 3.75952M i/s | 7.32080M i/s | 1.94727x | | 500 | 2.10754M i/s | 7.05963M i/s | 3.34970x | #### `Hash#shift` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 14.66444M i/s | 13.18876M i/s | 0.89937x | | 40 | 11.95124M i/s | 11.10420M i/s | 0.92913x | | 200 | 5.53681M i/s | 7.88155M i/s | 1.42348x | | 500 | 2.96728M i/s | 5.40405M i/s | 1.82121x | #### `Hash#dup` | Hash Size | Baseline | New | Factor | |----------:|--------------:|--------------:|-----------:| | 16 | 0.15063M i/s | 5.37889M i/s | 35.71024x | | 40 | 0.06515M i/s | 3.38196M i/s | 51.91279x | | 200 | 0.01359M i/s | 1.46538M i/s | 107.84056x | | 500 | 0.00559M i/s | 0.75411M i/s | 134.88057x | ### Binary Size Lower value is better. | File | Baseline | New | Factor | |:-----------|--------------:|--------------:|----------:| | mruby | 730,408B | 734,176B | 1.00519x | | libmruby.a | 1,068,134B | 1,072,846B | 1.00441x | ## Other Fixes The following issues have also been fixed in the parts where there was some change this time. * [Heap use-after-free in `Hash#value?`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-hash-value-md) * [Heap use-after-free in `ht_hash_equal`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-ht_hash_equal-md) * [Heap use-after-free in `ht_hash_func`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-ht_hash_func-md) * [Heap use-after-free in `mrb_hash_merge`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-heap-use-after-free-in-mrb_hash_merge-md) * [Self-replacement does not work for `Hash#replace`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-self-replacement-does-not-work-for-hash-replace-md) * [Repeated deletes and inserts increase memory usage of `Hash`](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-repeated-deletes-and-inserts-increase-memory-usage-of-hash-md) * [`Hash#rehash` does not reindex completely](https://gist.github.com/shuujii/30e4fcd5844a4112a0ecd4a5b3483101#file-hash-rehash-does-not-reindex-completely-md) * `mrb_hash_delete_key` does not cause an error for frozen object * `mrb_hash_new_capa` does not allocate required space first * [`mrb_os_memsize_of_hash_table` result is incorrect](https://github.com/mruby/mruby/pull/5032#discussion_r457994075)
2020-11-06Skip too big left shift in `flo_shift()`.Yukihiro "Matz" Matsumoto
2020-11-06Avoid negating `MRB_INT_MIN` which is impossible.Yukihiro "Matz" Matsumoto
2020-11-06Fix wrong integer casting.Yukihiro "Matz" Matsumoto
2020-11-05Fix a bug with printing `(null)` local variable name for a register.Yukihiro "Matz" Matsumoto
2020-11-05Fix `A.new([[1,2],3]).flatten` to return `Array`.Yukihiro "Matz" Matsumoto
2020-11-05Use `INT32_{MAX,MIN}` to specify integer ranges.Yukihiro "Matz" Matsumoto
2020-11-05Add `Array.new([1,2,3])` initialization.Yukihiro "Matz" Matsumoto
2020-11-04Avoid integer overflow in comparison.Yukihiro "Matz" Matsumoto
2020-11-04Add cast to silence int conversion warnings.Yukihiro "Matz" Matsumoto
2020-11-04Fix a bug with big negative integers.Yukihiro "Matz" Matsumoto
2020-11-04Update `mruby3.md` about new instructions.Yukihiro "Matz" Matsumoto
2020-11-04Add a new instruction `OP_LOADI32`.Yukihiro "Matz" Matsumoto
That loads 32 bit integer bypassing pool access.
2020-11-03Merge pull request #5113 from ↵Yukihiro "Matz" Matsumoto
shuujii/reduce-recompilation-when-updating-presym-target-files Reduce recompilation when updating presym target files
2020-11-03Merge pull request #5112 from shuujii/fix-dependencies-of-y.tab.oYukihiro "Matz" Matsumoto
Fix dependencies of `y.tab.o`
2020-11-03Use C99 `__func__` instead of `__FUNCTION__`; #5107Yukihiro "Matz" Matsumoto
2020-11-03Reduce recompilation when updating presym target filesKOBAYASHI Shuji
Fix that updating presym target files would recompile almost all files even if symbols did not change.
2020-11-03Fix dependencies of `y.tab.o`KOBAYASHI Shuji
In the case of `y.tab.o`, `y.tab.d` was not read, so `y.tab.c` was not recompiled by updating header files. It seemed that the cause was overwriting the rake rule, so I deleted unnecessary settings.
2020-11-03Add new instructions to handle symbols/literals >255; fix #5109Yukihiro "Matz" Matsumoto
New instructions: * OP_LOADL16 * OP_LOADSYM16 * OP_STRING16 Size of pools, symbols are `int16_t` but offset representation in the bytecode was 8 bits. Size of child `irep` array is `int16_t`, too but this change does not address it.
2020-11-02format '%p' expects argument of type 'void *'; #5107Yukihiro "Matz" Matsumoto
2020-11-02ISO C does not allow extra ';' outside of a function; #5107Yukihiro "Matz" Matsumoto
2020-11-02Revert "Remove long-time deprecated `minirake`."Yukihiro "Matz" Matsumoto
`minirake` was still used in many occasions. This reverts commit 3847c7eb64229b13b72e3a15f30b04b1f9a09c3e.
2020-11-02Search gem from `MRUBY_ROOT` if build config is in `build_config`.Yukihiro "Matz" Matsumoto
2020-11-02Make Ranges frozen as Ruby3.0.Yukihiro "Matz" Matsumoto
2020-11-02Replace `R-assignment` by `single-line pattern matching`.Yukihiro "Matz" Matsumoto
Since `R-assignment` in CRuby is abandoned. Single-line pattern matching in `mruby` only matches single local variable at the moment. Currently it works as a right assignment to a local variable. It will be enhanced in the future.
2020-11-02Update the build description in `mruby3.md`.Yukihiro "Matz" Matsumoto
2020-11-02Merge pull request #5111 from shuujii/fix-parallel-buildYukihiro "Matz" Matsumoto
Fix parallel build
2020-11-02Fix parallel buildKOBAYASHI Shuji
When `rake -m` and so on are used to build in parallel, building may be started before presym files are generated. Then, for example, the following error occurs and this issue is fixed. ```console In file included from /Users/shuujii/mruby/mruby/include/mruby.h:92: /mruby/mruby/include/mruby/presym.h:16:10: fatal error: '../build/presym.inc' file not found #include <../build/presym.inc> ^~~~~~~~~~~~~~~~~~~~~ ```
2020-11-01Merge pull request #5110 from bshastry/fix-mruby-ossfuzz-buildYukihiro "Matz" Matsumoto
ossfuzz: Fix mruby include paths
2020-11-01ossfuzz: Fix mruby include pathsBhargava Shastry
2020-11-01Merge pull request #5108 from mimaki/display_preview_versionYukihiro "Matz" Matsumoto
Add `preview` to version.
2020-11-01Fix `mruby -v option` test.mimaki
2020-11-01Add `preview` to version.mimaki
2020-10-30Fix the condition to detect core mrbgems.Yukihiro "Matz" Matsumoto
2020-10-29Exclude symbols from `mruby-test` gem only used for tests.Yukihiro "Matz" Matsumoto
2020-10-29Use `mrb` dump format for non core mrbgems by default.Yukihiro "Matz" Matsumoto
If you confirm the gem is cdump safe, add `spec.enable_cdump` in `mrbgem.rake` file. Some external gems e.g. `mruby-mgem-template` do not work with cdump.
2020-10-29Use clear `if` instead of `unless` for condition.Yukihiro "Matz" Matsumoto
2020-10-29Use instance variable `@dir` instead of access method `dir`.Yukihiro "Matz" Matsumoto
2020-10-29Remove `mrblib_dir` and `objs_dir` configuration from gems.Yukihiro "Matz" Matsumoto
Always use `mrblib` and 'src` for directory names.
2020-10-29Merge pull request #5105 from shuujii/fix-typo-in-Range-lastYukihiro "Matz" Matsumoto
Fix typo in `Range#last`
2020-10-29Merge pull request #5104 from shuujii/fix-typo-in-doc-guides-compile.mdYukihiro "Matz" Matsumoto
Fix typo in `doc/guides/compile.md` [ci skip]
2020-10-29Fix typo in `Range#last`KOBAYASHI Shuji
2020-10-29Fix typo in `doc/guides/compile.md` [ci skip]KOBAYASHI Shuji
2020-10-29Use `default' gembox by default.Yukihiro "Matz" Matsumoto
I changed to use `full-core` gembox for debugging. It should have been reverted before `mruby3` branch was merged.
2020-10-29Remove long-time deprecated `minirake`.Yukihiro "Matz" Matsumoto
2020-10-29The path of the gem should be relative from `MRUBY_ROOT`.Yukihiro "Matz" Matsumoto
It was relative from the directory of the build configuration file, but the document says it's relative from `MRUBY_ROOT`. When the default configuration file was `MRUBY_ROOT/build_config.rb`, it was OK for most of the cases.
2020-10-29Move `build_config.rb` -> `build_config/default.rb`; ref #5098Yukihiro "Matz" Matsumoto
In addition, update the documents referring `build_config.rb` which is no longer used. The new `build_config.rb` describes the new configuration structure in the comment.
2020-10-29Restore original name for default `build_config_name`; ref #5098Yukihiro "Matz" Matsumoto
2020-10-29Use `Dir.glob` instead of `map`.Yukihiro "Matz" Matsumoto
2020-10-29Add beginless/endless ranges tests.Yukihiro "Matz" Matsumoto
generated by cgit v1.2.3 (git 2.39.1) at 2026-09-10 18:52:31 +0000