Project

General

Profile

Actions

Feature #15631

closed

Let round_capa for ID table not allocate excess capacity for power of 2 ints >= 4

Added by ahorek (Pavel Rosický) about 3 years ago. Updated over 2 years ago.

Status:
Closed
Priority:
Normal
Target version:
-
[ruby-core:91651]

Description

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

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) id_table.c.patch ahorek (Pavel Rosický), 03/01/2019 01:22 PM
st.c.patch (455 Bytes) st.c.patch ahorek (Pavel Rosický), 07/19/2019 03:15 PM
st.c.patch (434 Bytes) st.c.patch v2 ahorek (Pavel Rosický), 07/21/2019 12:52 AM
Actions

Also available in: Atom PDF