* [ruby-core:91651] [Ruby trunk Feature#15631] Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
[not found] <redmine.issue-15631.20190301134826@ruby-lang.org>
@ 2019-03-01 13:48 ` pdahorek
2019-03-11 10:53 ` [ruby-core:91773] " lourens
` (7 subsequent siblings)
8 siblings, 0 replies; 9+ messages in thread
From: pdahorek @ 2019-03-01 13:48 UTC (permalink / raw)
To: ruby-core
Issue #15631 has been reported by ahorek (Pavel Rosický).
----------------------------------------
Feature #15631: Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
https://bugs.ruby-lang.org/issues/15631
* Author: ahorek (Pavel Rosický)
* Status: Open
* Priority: Normal
* Assignee:
* Target version:
----------------------------------------
right now round_capa value is rounded up to the next power of 2
```
round_capa(4) -> returns 8
round_capa(8) -> returns 16
round_capa(16) -> returns 32
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
it seems wasteful to allocate the extra items capacity, so this PR changes that to
```
round_capa(4) -> returns 4
round_capa(8) -> returns 8
round_capa(16) -> returns 16
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
the main purpose is to reduce memory usage especially during boot
my patch also uses BUILTIN_CLZ macro instead of hash shifts that makes it slightly faster
here's a benchmark
```ruby
require 'benchmark/ips'
Benchmark.ips do |x|
x.config(time: 20, warmup: 3)
x.report('struct', "Struct.new(*('a'..'z').map { |x| x.to_sym })")
end
```
```
trunk
Warming up --------------------------------------
struct 527.000 i/100ms
Calculating -------------------------------------
struct 5.461k (± 5.5%) i/s - 109.089k in 20.040253s
methodmising - POW2_P (github)
Warming up --------------------------------------
struct 544.000 i/100ms
Calculating -------------------------------------
struct 5.570k (± 4.1%) i/s - 111.520k in 20.057245s
ahorek - BUILTIN_CLZ (id_table.c.patch)
Warming up --------------------------------------
struct 571.000 i/100ms
Calculating -------------------------------------
struct 5.812k (± 3.6%) i/s - 116.484k in 20.070607s
```
discussion https://github.com/ruby/ruby/pull/2083
---Files--------------------------------
id_table.c.patch (534 Bytes)
--
https://bugs.ruby-lang.org/
Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>
^ permalink raw reply [flat|nested] 9+ messages in thread
* [ruby-core:91773] [Ruby trunk Feature#15631] Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
[not found] <redmine.issue-15631.20190301134826@ruby-lang.org>
2019-03-01 13:48 ` [ruby-core:91651] [Ruby trunk Feature#15631] Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4 pdahorek
@ 2019-03-11 10:53 ` lourens
2019-07-11 7:34 ` [ruby-core:93673] [Ruby master " ko1
` (6 subsequent siblings)
8 siblings, 0 replies; 9+ messages in thread
From: lourens @ 2019-03-11 10:53 UTC (permalink / raw)
To: ruby-core
Issue #15631 has been updated by methodmissing (Lourens Naudé).
Thanks for raising this Pavel.
`st_init_table_with_size(0)` effectively also allocates additional capacity, but if and how quickly the hash tables mutate I'll investigate later.
References https://github.com/ruby/ruby/blob/trunk/st.c#L573-L578 , https://github.com/ruby/ruby/blob/trunk/st.c#L595 and https://github.com/ruby/ruby/blob/trunk/st.c#L332-L359
A simple peek suggests a total table size of 152 bytes on init, but will investigate time to mutation of these 0 sized tables this evening:
```
diff --git a/st.c b/st.c
index ed235c674e..f2b99d7771 100644
--- a/st.c
+++ b/st.c
@@ -615,6 +615,8 @@ st_init_table_with_size(const struct st_hash_type *type, st_index_t size)
#ifdef ST_DEBUG
st_check(tab);
#endif
+ printf("# st_init_table_with_size(%d) -> %d (%d)\n", size, n, st_memsize(tab));
+
return tab;
}
```
```
linking miniruby
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(102) -> 7 (3384)
# st_init_table_with_size(255) -> 8 (7224)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(1000) -> 10 (28728)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(1000) -> 10 (28728)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(7) -> 3 (248)
# st_init_table_with_size(15) -> 4 (440)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(16) -> 5 (888)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
# st_init_table_with_size(0) -> 2 (152)
```
ahorek (Pavel Rosický) wrote:
> right now round_capa value is rounded up to the next power of 2
> ```
> round_capa(4) -> returns 8
> round_capa(8) -> returns 16
> round_capa(16) -> returns 32
>
> round_capa(5) -> returns 8
> round_capa(9) -> returns 16
> round_capa(17) -> returns 32
> etc.
> ```
>
> it seems wasteful to allocate the extra items capacity, so this PR changes that to
> ```
> round_capa(4) -> returns 4
> round_capa(8) -> returns 8
> round_capa(16) -> returns 16
>
> round_capa(5) -> returns 8
> round_capa(9) -> returns 16
> round_capa(17) -> returns 32
> etc.
> ```
>
> the main purpose is to reduce memory usage especially during boot
>
> my patch also uses BUILTIN_CLZ macro instead of shifts that makes it slightly faster
>
> here's a benchmark
> ```ruby
> require 'benchmark/ips'
>
> Benchmark.ips do |x|
> x.config(time: 20, warmup: 3)
>
> x.report('struct', "Struct.new(*('a'..'z').map { |x| x.to_sym })")
> end
> ```
>
> ```
> trunk
> Warming up --------------------------------------
> struct 527.000 i/100ms
> Calculating -------------------------------------
> struct 5.461k (± 5.5%) i/s - 109.089k in 20.040253s
>
> methodmising - POW2_P (github)
> Warming up --------------------------------------
> struct 544.000 i/100ms
> Calculating -------------------------------------
> struct 5.570k (± 4.1%) i/s - 111.520k in 20.057245s
>
> ahorek - BUILTIN_CLZ (id_table.c.patch)
> Warming up --------------------------------------
> struct 571.000 i/100ms
> Calculating -------------------------------------
> struct 5.812k (± 3.6%) i/s - 116.484k in 20.070607s
> ```
>
> discussion https://github.com/ruby/ruby/pull/2083
----------------------------------------
Feature #15631: Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
https://bugs.ruby-lang.org/issues/15631#change-77049
* Author: ahorek (Pavel Rosický)
* Status: Open
* Priority: Normal
* Assignee:
* Target version:
----------------------------------------
right now round_capa value is rounded up to the next power of 2
```
round_capa(4) -> returns 8
round_capa(8) -> returns 16
round_capa(16) -> returns 32
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
it seems wasteful to allocate the extra items capacity, so this PR changes that to
```
round_capa(4) -> returns 4
round_capa(8) -> returns 8
round_capa(16) -> returns 16
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
the main purpose is to reduce memory usage especially during boot
my patch also uses BUILTIN_CLZ macro instead of shifts that makes it slightly faster
here's a benchmark
```ruby
require 'benchmark/ips'
Benchmark.ips do |x|
x.config(time: 20, warmup: 3)
x.report('struct', "Struct.new(*('a'..'z').map { |x| x.to_sym })")
end
```
```
trunk
Warming up --------------------------------------
struct 527.000 i/100ms
Calculating -------------------------------------
struct 5.461k (± 5.5%) i/s - 109.089k in 20.040253s
methodmising - POW2_P (github)
Warming up --------------------------------------
struct 544.000 i/100ms
Calculating -------------------------------------
struct 5.570k (± 4.1%) i/s - 111.520k in 20.057245s
ahorek - BUILTIN_CLZ (id_table.c.patch)
Warming up --------------------------------------
struct 571.000 i/100ms
Calculating -------------------------------------
struct 5.812k (± 3.6%) i/s - 116.484k in 20.070607s
```
discussion https://github.com/ruby/ruby/pull/2083
---Files--------------------------------
id_table.c.patch (534 Bytes)
--
https://bugs.ruby-lang.org/
Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [ruby-core:93673] [Ruby master Feature#15631] Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
[not found] <redmine.issue-15631.20190301134826@ruby-lang.org>
2019-03-01 13:48 ` [ruby-core:91651] [Ruby trunk Feature#15631] Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4 pdahorek
2019-03-11 10:53 ` [ruby-core:91773] " lourens
@ 2019-07-11 7:34 ` ko1
2019-07-18 23:55 ` [ruby-core:93838] " pdahorek
` (5 subsequent siblings)
8 siblings, 0 replies; 9+ messages in thread
From: ko1 @ 2019-07-11 7:34 UTC (permalink / raw)
To: ruby-core
Issue #15631 has been updated by ko1 (Koichi Sasada).
Assignee set to ko1 (Koichi Sasada)
funny_falcon, do you have any opinion?
if no opinion, we'll discuss it one month later and will commit it.
in fact, I can't check algorithm, so we can try it.
ahorek:
could you give me more performance measurements?
* you should not call `map` in iteration (you should prepare IDs before)
* now you only measures 26 fields. could you measure other numbers, 1 to 50, for example.
Thanks,
Koichi
----------------------------------------
Feature #15631: Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
https://bugs.ruby-lang.org/issues/15631#change-79284
* Author: ahorek (Pavel Rosický)
* Status: Open
* Priority: Normal
* Assignee: ko1 (Koichi Sasada)
* Target version:
----------------------------------------
right now round_capa value is rounded up to the next power of 2
```
round_capa(4) -> returns 8
round_capa(8) -> returns 16
round_capa(16) -> returns 32
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
it seems wasteful to allocate the extra items capacity, so this PR changes that to
```
round_capa(4) -> returns 4
round_capa(8) -> returns 8
round_capa(16) -> returns 16
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
the main purpose is to reduce memory usage especially during boot
my patch also uses BUILTIN_CLZ macro instead of shifts that makes it slightly faster
here's a benchmark
```ruby
require 'benchmark/ips'
Benchmark.ips do |x|
x.config(time: 20, warmup: 3)
x.report('struct', "Struct.new(*('a'..'z').map { |x| x.to_sym })")
end
```
```
trunk
Warming up --------------------------------------
struct 527.000 i/100ms
Calculating -------------------------------------
struct 5.461k (± 5.5%) i/s - 109.089k in 20.040253s
methodmising - POW2_P (github)
Warming up --------------------------------------
struct 544.000 i/100ms
Calculating -------------------------------------
struct 5.570k (± 4.1%) i/s - 111.520k in 20.057245s
ahorek - BUILTIN_CLZ (id_table.c.patch)
Warming up --------------------------------------
struct 571.000 i/100ms
Calculating -------------------------------------
struct 5.812k (± 3.6%) i/s - 116.484k in 20.070607s
```
discussion https://github.com/ruby/ruby/pull/2083
---Files--------------------------------
id_table.c.patch (534 Bytes)
--
https://bugs.ruby-lang.org/
Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>
^ permalink raw reply [flat|nested] 9+ messages in thread
* [ruby-core:93838] [Ruby master Feature#15631] Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
[not found] <redmine.issue-15631.20190301134826@ruby-lang.org>
` (2 preceding siblings ...)
2019-07-11 7:34 ` [ruby-core:93673] [Ruby master " ko1
@ 2019-07-18 23:55 ` pdahorek
2019-07-19 15:23 ` [ruby-core:93846] " pdahorek
` (4 subsequent siblings)
8 siblings, 0 replies; 9+ messages in thread
From: pdahorek @ 2019-07-18 23:55 UTC (permalink / raw)
To: ruby-core
Issue #15631 has been updated by ahorek (Pavel Rosický).
Thanks for the review Koichi. I tested the patch on a rails app (redmine), but unfortunatelly there's no improvement.
0.1MB less memory after boot (^150MB total)
No mesurable difference in performance
I'll investigate the second case. Hash creation might be a better place to optimize.
----------------------------------------
Feature #15631: Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
https://bugs.ruby-lang.org/issues/15631#change-79717
* Author: ahorek (Pavel Rosický)
* Status: Open
* Priority: Normal
* Assignee: ko1 (Koichi Sasada)
* Target version:
----------------------------------------
right now round_capa value is rounded up to the next power of 2
```
round_capa(4) -> returns 8
round_capa(8) -> returns 16
round_capa(16) -> returns 32
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
it seems wasteful to allocate the extra items capacity, so this PR changes that to
```
round_capa(4) -> returns 4
round_capa(8) -> returns 8
round_capa(16) -> returns 16
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
the main purpose is to reduce memory usage especially during boot
my patch also uses BUILTIN_CLZ macro instead of shifts that makes it slightly faster
here's a benchmark
```ruby
require 'benchmark/ips'
Benchmark.ips do |x|
x.config(time: 20, warmup: 3)
x.report('struct', "Struct.new(*('a'..'z').map { |x| x.to_sym })")
end
```
```
trunk
Warming up --------------------------------------
struct 527.000 i/100ms
Calculating -------------------------------------
struct 5.461k (± 5.5%) i/s - 109.089k in 20.040253s
methodmising - POW2_P (github)
Warming up --------------------------------------
struct 544.000 i/100ms
Calculating -------------------------------------
struct 5.570k (± 4.1%) i/s - 111.520k in 20.057245s
ahorek - BUILTIN_CLZ (id_table.c.patch)
Warming up --------------------------------------
struct 571.000 i/100ms
Calculating -------------------------------------
struct 5.812k (± 3.6%) i/s - 116.484k in 20.070607s
```
discussion https://github.com/ruby/ruby/pull/2083
---Files--------------------------------
id_table.c.patch (534 Bytes)
--
https://bugs.ruby-lang.org/
Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>
^ permalink raw reply [flat|nested] 9+ messages in thread
* [ruby-core:93846] [Ruby master Feature#15631] Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
[not found] <redmine.issue-15631.20190301134826@ruby-lang.org>
` (3 preceding siblings ...)
2019-07-18 23:55 ` [ruby-core:93838] " pdahorek
@ 2019-07-19 15:23 ` pdahorek
2019-07-20 2:00 ` [ruby-core:93856] " nobu
` (3 subsequent siblings)
8 siblings, 0 replies; 9+ messages in thread
From: pdahorek @ 2019-07-19 15:23 UTC (permalink / raw)
To: ruby-core
Issue #15631 has been updated by ahorek (Pavel Rosický).
File st.c.patch added
I've attached the second patch for st_init_table_with_size. In theory it should be faster, but I can't measure any difference in ruby.
----------------------------------------
Feature #15631: Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
https://bugs.ruby-lang.org/issues/15631#change-79729
* Author: ahorek (Pavel Rosický)
* Status: Open
* Priority: Normal
* Assignee: ko1 (Koichi Sasada)
* Target version:
----------------------------------------
right now round_capa value is rounded up to the next power of 2
```
round_capa(4) -> returns 8
round_capa(8) -> returns 16
round_capa(16) -> returns 32
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
it seems wasteful to allocate the extra items capacity, so this PR changes that to
```
round_capa(4) -> returns 4
round_capa(8) -> returns 8
round_capa(16) -> returns 16
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
the main purpose is to reduce memory usage especially during boot
my patch also uses BUILTIN_CLZ macro instead of shifts that makes it slightly faster
here's a benchmark
```ruby
require 'benchmark/ips'
Benchmark.ips do |x|
x.config(time: 20, warmup: 3)
x.report('struct', "Struct.new(*('a'..'z').map { |x| x.to_sym })")
end
```
```
trunk
Warming up --------------------------------------
struct 527.000 i/100ms
Calculating -------------------------------------
struct 5.461k (± 5.5%) i/s - 109.089k in 20.040253s
methodmising - POW2_P (github)
Warming up --------------------------------------
struct 544.000 i/100ms
Calculating -------------------------------------
struct 5.570k (± 4.1%) i/s - 111.520k in 20.057245s
ahorek - BUILTIN_CLZ (id_table.c.patch)
Warming up --------------------------------------
struct 571.000 i/100ms
Calculating -------------------------------------
struct 5.812k (± 3.6%) i/s - 116.484k in 20.070607s
```
discussion https://github.com/ruby/ruby/pull/2083
---Files--------------------------------
id_table.c.patch (534 Bytes)
st.c.patch (455 Bytes)
--
https://bugs.ruby-lang.org/
Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>
^ permalink raw reply [flat|nested] 9+ messages in thread
* [ruby-core:93856] [Ruby master Feature#15631] Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
[not found] <redmine.issue-15631.20190301134826@ruby-lang.org>
` (4 preceding siblings ...)
2019-07-19 15:23 ` [ruby-core:93846] " pdahorek
@ 2019-07-20 2:00 ` nobu
2019-07-20 22:58 ` [ruby-core:93861] " lourens
` (2 subsequent siblings)
8 siblings, 0 replies; 9+ messages in thread
From: nobu @ 2019-07-20 2:00 UTC (permalink / raw)
To: ruby-core
Issue #15631 has been updated by nobu (Nobuyoshi Nakada).
It should use `SIZEOF_ST_INDEX_T` and `nlz_intptr`.
----------------------------------------
Feature #15631: Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
https://bugs.ruby-lang.org/issues/15631#change-79755
* Author: ahorek (Pavel Rosický)
* Status: Open
* Priority: Normal
* Assignee: ko1 (Koichi Sasada)
* Target version:
----------------------------------------
right now round_capa value is rounded up to the next power of 2
```
round_capa(4) -> returns 8
round_capa(8) -> returns 16
round_capa(16) -> returns 32
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
it seems wasteful to allocate the extra items capacity, so this PR changes that to
```
round_capa(4) -> returns 4
round_capa(8) -> returns 8
round_capa(16) -> returns 16
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
the main purpose is to reduce memory usage especially during boot
my patch also uses BUILTIN_CLZ macro instead of shifts that makes it slightly faster
here's a benchmark
```ruby
require 'benchmark/ips'
Benchmark.ips do |x|
x.config(time: 20, warmup: 3)
x.report('struct', "Struct.new(*('a'..'z').map { |x| x.to_sym })")
end
```
```
trunk
Warming up --------------------------------------
struct 527.000 i/100ms
Calculating -------------------------------------
struct 5.461k (± 5.5%) i/s - 109.089k in 20.040253s
methodmising - POW2_P (github)
Warming up --------------------------------------
struct 544.000 i/100ms
Calculating -------------------------------------
struct 5.570k (± 4.1%) i/s - 111.520k in 20.057245s
ahorek - BUILTIN_CLZ (id_table.c.patch)
Warming up --------------------------------------
struct 571.000 i/100ms
Calculating -------------------------------------
struct 5.812k (± 3.6%) i/s - 116.484k in 20.070607s
```
discussion https://github.com/ruby/ruby/pull/2083
---Files--------------------------------
id_table.c.patch (534 Bytes)
st.c.patch (455 Bytes)
--
https://bugs.ruby-lang.org/
Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>
^ permalink raw reply [flat|nested] 9+ messages in thread
* [ruby-core:93861] [Ruby master Feature#15631] Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
[not found] <redmine.issue-15631.20190301134826@ruby-lang.org>
` (5 preceding siblings ...)
2019-07-20 2:00 ` [ruby-core:93856] " nobu
@ 2019-07-20 22:58 ` lourens
2019-07-29 6:02 ` [ruby-core:93963] " ko1
2019-07-31 18:51 ` [ruby-core:94082] " pdahorek
8 siblings, 0 replies; 9+ messages in thread
From: lourens @ 2019-07-20 22:58 UTC (permalink / raw)
To: ruby-core
Issue #15631 has been updated by methodmissing (Lourens Naudé).
Pavel added a new patch for `get_power2` in https://github.com/ruby/ruby/pull/2292
----------------------------------------
Feature #15631: Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
https://bugs.ruby-lang.org/issues/15631#change-79773
* Author: ahorek (Pavel Rosický)
* Status: Open
* Priority: Normal
* Assignee: ko1 (Koichi Sasada)
* Target version:
----------------------------------------
right now round_capa value is rounded up to the next power of 2
```
round_capa(4) -> returns 8
round_capa(8) -> returns 16
round_capa(16) -> returns 32
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
it seems wasteful to allocate the extra items capacity, so this PR changes that to
```
round_capa(4) -> returns 4
round_capa(8) -> returns 8
round_capa(16) -> returns 16
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
the main purpose is to reduce memory usage especially during boot
my patch also uses BUILTIN_CLZ macro instead of shifts that makes it slightly faster
here's a benchmark
```ruby
require 'benchmark/ips'
Benchmark.ips do |x|
x.config(time: 20, warmup: 3)
x.report('struct', "Struct.new(*('a'..'z').map { |x| x.to_sym })")
end
```
```
trunk
Warming up --------------------------------------
struct 527.000 i/100ms
Calculating -------------------------------------
struct 5.461k (± 5.5%) i/s - 109.089k in 20.040253s
methodmising - POW2_P (github)
Warming up --------------------------------------
struct 544.000 i/100ms
Calculating -------------------------------------
struct 5.570k (± 4.1%) i/s - 111.520k in 20.057245s
ahorek - BUILTIN_CLZ (id_table.c.patch)
Warming up --------------------------------------
struct 571.000 i/100ms
Calculating -------------------------------------
struct 5.812k (± 3.6%) i/s - 116.484k in 20.070607s
```
discussion https://github.com/ruby/ruby/pull/2083
---Files--------------------------------
id_table.c.patch (534 Bytes)
st.c.patch (455 Bytes)
--
https://bugs.ruby-lang.org/
Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>
^ permalink raw reply [flat|nested] 9+ messages in thread
* [ruby-core:93963] [Ruby master Feature#15631] Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
[not found] <redmine.issue-15631.20190301134826@ruby-lang.org>
` (6 preceding siblings ...)
2019-07-20 22:58 ` [ruby-core:93861] " lourens
@ 2019-07-29 6:02 ` ko1
2019-07-31 18:51 ` [ruby-core:94082] " pdahorek
8 siblings, 0 replies; 9+ messages in thread
From: ko1 @ 2019-07-29 6:02 UTC (permalink / raw)
To: ruby-core
Issue #15631 has been updated by ko1 (Koichi Sasada).
pls give us your measurements. We can't understand how it is useful.
Thanks,
Koichi
----------------------------------------
Feature #15631: Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
https://bugs.ruby-lang.org/issues/15631#change-80154
* Author: ahorek (Pavel Rosický)
* Status: Open
* Priority: Normal
* Assignee: ko1 (Koichi Sasada)
* Target version:
----------------------------------------
right now round_capa value is rounded up to the next power of 2
```
round_capa(4) -> returns 8
round_capa(8) -> returns 16
round_capa(16) -> returns 32
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
it seems wasteful to allocate the extra items capacity, so this PR changes that to
```
round_capa(4) -> returns 4
round_capa(8) -> returns 8
round_capa(16) -> returns 16
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
the main purpose is to reduce memory usage especially during boot
my patch also uses BUILTIN_CLZ macro instead of shifts that makes it slightly faster
here's a benchmark
```ruby
require 'benchmark/ips'
Benchmark.ips do |x|
x.config(time: 20, warmup: 3)
x.report('struct', "Struct.new(*('a'..'z').map { |x| x.to_sym })")
end
```
```
trunk
Warming up --------------------------------------
struct 527.000 i/100ms
Calculating -------------------------------------
struct 5.461k (± 5.5%) i/s - 109.089k in 20.040253s
methodmising - POW2_P (github)
Warming up --------------------------------------
struct 544.000 i/100ms
Calculating -------------------------------------
struct 5.570k (± 4.1%) i/s - 111.520k in 20.057245s
ahorek - BUILTIN_CLZ (id_table.c.patch)
Warming up --------------------------------------
struct 571.000 i/100ms
Calculating -------------------------------------
struct 5.812k (± 3.6%) i/s - 116.484k in 20.070607s
```
discussion https://github.com/ruby/ruby/pull/2083
---Files--------------------------------
id_table.c.patch (534 Bytes)
st.c.patch (455 Bytes)
st.c.patch (434 Bytes)
--
https://bugs.ruby-lang.org/
Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>
^ permalink raw reply [flat|nested] 9+ messages in thread
* [ruby-core:94082] [Ruby master Feature#15631] Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
[not found] <redmine.issue-15631.20190301134826@ruby-lang.org>
` (7 preceding siblings ...)
2019-07-29 6:02 ` [ruby-core:93963] " ko1
@ 2019-07-31 18:51 ` pdahorek
8 siblings, 0 replies; 9+ messages in thread
From: pdahorek @ 2019-07-31 18:51 UTC (permalink / raw)
To: ruby-core
Issue #15631 has been updated by ahorek (Pavel Rosický).
I run several benchmark suites for both patches
https://github.com/ruby-bench/ruby-bench-suite
https://github.com/schneems/derailed_benchmarks
but all differences were within margin of error. Here's an optimized assembly comparsion that explains why:
https://user-images.githubusercontent.com/9540855/62237913-2e221380-b3d2-11e9-932a-14b09038bf91.png
saving 1-2 instructions makes no real difference.
feel free to close the issue. Thanks
----------------------------------------
Feature #15631: Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4
https://bugs.ruby-lang.org/issues/15631#change-80313
* Author: ahorek (Pavel Rosický)
* Status: Open
* Priority: Normal
* Assignee: ko1 (Koichi Sasada)
* Target version:
----------------------------------------
right now round_capa value is rounded up to the next power of 2
```
round_capa(4) -> returns 8
round_capa(8) -> returns 16
round_capa(16) -> returns 32
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
it seems wasteful to allocate the extra items capacity, so this PR changes that to
```
round_capa(4) -> returns 4
round_capa(8) -> returns 8
round_capa(16) -> returns 16
round_capa(5) -> returns 8
round_capa(9) -> returns 16
round_capa(17) -> returns 32
etc.
```
the main purpose is to reduce memory usage especially during boot
my patch also uses BUILTIN_CLZ macro instead of shifts that makes it slightly faster
here's a benchmark
```ruby
require 'benchmark/ips'
Benchmark.ips do |x|
x.config(time: 20, warmup: 3)
x.report('struct', "Struct.new(*('a'..'z').map { |x| x.to_sym })")
end
```
```
trunk
Warming up --------------------------------------
struct 527.000 i/100ms
Calculating -------------------------------------
struct 5.461k (± 5.5%) i/s - 109.089k in 20.040253s
methodmising - POW2_P (github)
Warming up --------------------------------------
struct 544.000 i/100ms
Calculating -------------------------------------
struct 5.570k (± 4.1%) i/s - 111.520k in 20.057245s
ahorek - BUILTIN_CLZ (id_table.c.patch)
Warming up --------------------------------------
struct 571.000 i/100ms
Calculating -------------------------------------
struct 5.812k (± 3.6%) i/s - 116.484k in 20.070607s
```
discussion https://github.com/ruby/ruby/pull/2083
---Files--------------------------------
id_table.c.patch (534 Bytes)
st.c.patch (455 Bytes)
st.c.patch (434 Bytes)
--
https://bugs.ruby-lang.org/
Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2019-07-31 18:52 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <redmine.issue-15631.20190301134826@ruby-lang.org>
2019-03-01 13:48 ` [ruby-core:91651] [Ruby trunk Feature#15631] Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4 pdahorek
2019-03-11 10:53 ` [ruby-core:91773] " lourens
2019-07-11 7:34 ` [ruby-core:93673] [Ruby master " ko1
2019-07-18 23:55 ` [ruby-core:93838] " pdahorek
2019-07-19 15:23 ` [ruby-core:93846] " pdahorek
2019-07-20 2:00 ` [ruby-core:93856] " nobu
2019-07-20 22:58 ` [ruby-core:93861] " lourens
2019-07-29 6:02 ` [ruby-core:93963] " ko1
2019-07-31 18:51 ` [ruby-core:94082] " pdahorek
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).