Forum: Ruby-core [Ruby 1.9 - Feature #5033][Open] PATCH: 1.9: gc_mark_children: Avoid gc_mark() tail recursion, use g

Issue #5033 has been reported by Kurt  Stephens.

----------------------------------------
Feature #5033: PATCH: 1.9: gc_mark_children: Avoid gc_mark() tail 
recursion, use goto again.
http://redmine.ruby-lang.org/issues/5033

Author: Kurt  Stephens
Status: Open
Priority: Normal
Assignee:
Category:
Target version: 1.9.x


Minor GC improvement.

Avoid recurring into gc_mark() when "goto again;" is sufficient.

-- KAS

Issue #5033 has been updated by Motohiro KOSAKI.

Category set to core
Status changed from Open to Assigned
Assignee set to Narihiro Nakamura


----------------------------------------
Feature #5033: PATCH: 1.9: gc_mark_children: Avoid gc_mark() tail 
recursion, use goto again.
http://redmine.ruby-lang.org/issues/5033

Author: Kurt  Stephens
Status: Assigned
Priority: Normal
Assignee: Narihiro Nakamura
Category: core
Target version: 1.9.x


Minor GC improvement.

Avoid recurring into gc_mark() when "goto again;" is sufficient.

-- KAS

Issue #5033 has been updated by Shyouhei Urabe.


-1 I believe my compiler is smart enough to do that optimization and 
goto is considered harmful.
----------------------------------------
Feature #5033: PATCH: 1.9: gc_mark_children: Avoid gc_mark() tail 
recursion, use goto again.
http://redmine.ruby-lang.org/issues/5033

Author: Kurt  Stephens
Status: Assigned
Priority: Normal
Assignee: Narihiro Nakamura
Category: core
Target version: 1.9.x


Minor GC improvement.

Avoid recurring into gc_mark() when "goto again;" is sufficient.

-- KAS

Issue #5033 has been updated by Kurt  Stephens.


Not aware of any compiler that is smart enough to optimize away the 
second half of gc_mark() (lines 1616-1628), when tail called from 
gc_mark_children().

gc_mark_children() already uses goto.

----------------------------------------
Feature #5033: PATCH: 1.9: gc_mark_children: Avoid gc_mark() tail 
recursion, use goto again.
http://redmine.ruby-lang.org/issues/5033

Author: Kurt  Stephens
Status: Assigned
Priority: Normal
Assignee: Narihiro Nakamura
Category: core
Target version: 1.9.x


Minor GC improvement.

Avoid recurring into gc_mark() when "goto again;" is sufficient.

-- KAS

Issue #5033 has been updated by Yusuke Endoh.


Personally I don't think goto matters so much in GC implementation.
But I'm not sure if the patch is actually so effective.
Did you benchmark?  If you did, could you show it?

--
Yusuke Endoh <mame@tsg.ne.jp>
----------------------------------------
Feature #5033: PATCH: 1.9: gc_mark_children: Avoid gc_mark() tail 
recursion, use goto again.
http://redmine.ruby-lang.org/issues/5033

Author: Kurt  Stephens
Status: Assigned
Priority: Normal
Assignee: Narihiro Nakamura
Category: core
Target version: 1.9.x


Minor GC improvement.

Avoid recurring into gc_mark() when "goto again;" is sufficient.

-- KAS

Kurt Stephens <ks.ruby@kurtstephens.com> wrote:
> Feature #5033: PATCH: 1.9: gc_mark_children: Avoid gc_mark() tail recursion, use 
goto again.
> http://redmine.ruby-lang.org/issues/5033

In [ruby-core:36931], ko1 told us GC eats stack when marking nested
objects.  Kurt's patch should allow us to run smaller pthread stack
sizes while still supporting deeply-nested structures.

Kurt: can you test a smaller stack size with your patch with some
deeply-nested objects?

Thanks, I'm excited about this patch :D  (but unlikely to have time to 
test
until next week).

Issue #5033 has been updated by Kurt  Stephens.


I don't know of a reliable means to record max stack depth, but the 
speed isn't necessarily better or worse:

 > bash ./profile-gc-mark
+ export 'CFLAGS=-O2 -I/opt/local/include' LDFLAGS=-L/opt/local/lib
+ CFLAGS='-O2 -I/opt/local/include'
+ LDFLAGS=-L/opt/local/lib
+ for branch in trunk trunk-gc-mark-optimization
+ git checkout trunk
Switched to branch 'trunk'
Your branch is ahead of 'origin/trunk' by 10 commits.
+ prefix=/Users/stephens/local/ruby-trunk
+ make test
+ make test

real  0m51.808s
user  0m19.760s
sys  0m13.118s
+ make test

real  0m49.938s
user  0m19.598s
sys  0m13.396s
+ for branch in trunk trunk-gc-mark-optimization
+ git checkout trunk-gc-mark-optimization
Switched to branch 'trunk-gc-mark-optimization'
+ prefix=/Users/stephens/local/ruby-trunk-gc-mark-optimization
+ make test
+ make test

real  0m51.752s
user  0m19.526s
sys  0m13.336s
+ make test

real  0m50.157s
user  0m19.735s
sys  0m13.487s

BTW: make test-all in trunk hangs for me on OS X 64.

The space improvements would occur for NODES with deep 
obj->as.node.u3.node, arrays with deep last elements, and OBJECTS where 
the last IVAR is deep.

obj->as.file.fptr->write_lock, obj->as.regexp.src, obj->as.match.str, 
obj->as.rational.den, obj->as.complex.imag are likely to be not deep.

So maybe this patch is pointless, except for the removal of the 
unnecessary "long i" variable in the T_OBJECT case/loop.





----------------------------------------
Feature #5033: PATCH: 1.9: gc_mark_children: Avoid gc_mark() tail 
recursion, use goto again.
http://redmine.ruby-lang.org/issues/5033

Author: Kurt  Stephens
Status: Assigned
Priority: Normal
Assignee: Narihiro Nakamura
Category: core
Target version: 1.9.x


Minor GC improvement.

Avoid recurring into gc_mark() when "goto again;" is sufficient.

-- KAS

Eric Wong <normalperson@yhbt.net> wrote:
> Kurt Stephens <ks.ruby@kurtstephens.com> wrote:
> > Feature #5033: PATCH: 1.9: gc_mark_children: Avoid gc_mark() tail recursion, 
use goto again.
> > http://redmine.ruby-lang.org/issues/5033
>
> In [ruby-core:36931], ko1 told us GC eats stack when marking nested
> objects.  Kurt's patch should allow us to run smaller pthread stack
> sizes while still supporting deeply-nested structures.

shyouhei appears right about compilers being able to optimize this
for the easy cases.

However "inspect" on deeply-nested structures is still stack hungry and
causes SystemStackErrors on my machine if I try to "p" a deeply-nested
array or hash.

> Kurt: can you test a smaller stack size with your patch with some
> deeply-nested objects?

I was playing around with something like this (but did not
get any useful results/conclusion either way):

def deeper!(array_or_hash, depth)
  if depth > 6000
    $last = array_or_hash[0] = {}
  else
    array_or_hash[0] = [ deeper!({}, depth += 1) ]
  end
end

orig = {}
deeper!(orig, 0)
5000.times do |i|
  deeper!($last, 0)
end
p $$
# give GC something to much on
100000.times { |i| i.to_s }
p :done

>
> real  0m50.157s
> user  0m19.735s
> sys   0m13.487s

Hmm...
Don't you have any good result? Usually we reject the ticket if the
optimization patch
don't show any better result.

I'm waiting someone which is interesting this ticket post the result.
But, for remark, if nobody success to get it, I'll reject this.

Thanks.

Issue #5033 has been updated by Kurt  Stephens.


There is a time improvement for Arrays deeply nested at their tails:

Stock:

+ ./miniruby -e '
x = [ nil ]
10000000.times do | i |
  x[0] = [ i ]
  x = x[0]
end
puts :OK
system "ps -l -p #{$$}"
'
OK
  UID   PID  PPID        F CPU PRI NI       SZ    RSS WCHAN     S 
ADDR TTY           TIME CMD
  501 96240 84698     4006   0  31  0  2447588   3096 -      S+ 
fda67e0 ttys009    0:02.28 ./miniruby -e ^Jx = [

real  0m2.293s
user  0m2.275s
sys  0m0.013s


+ git checkout trunk-gc-mark-optimization
Switched to branch 'trunk-gc-mark-optimization'

+ ./miniruby -e '
x = [ nil ]
10000000.times do | i |
  x[0] = [ i ]
  x = x[0]
end
puts :OK
system "ps -l -p #{$$}"
'
OK
  UID   PID  PPID        F CPU PRI NI       SZ    RSS WCHAN     S 
ADDR TTY           TIME CMD
  501 20407 84698     4006   0  31  0  2456804   3096 -      S+ 
fda67e0 ttys009    0:02.08 ./miniruby -e ^Jx = [

real  0m2.096s
user  0m2.074s
sys  0m0.014s


----------------------------------------
Feature #5033: PATCH: 1.9: gc_mark_children: Avoid gc_mark() tail 
recursion, use goto again.
http://redmine.ruby-lang.org/issues/5033

Author: Kurt  Stephens
Status: Assigned
Priority: Normal
Assignee: Narihiro Nakamura
Category: core
Target version: 1.9.x


Minor GC improvement.

Avoid recurring into gc_mark() when "goto again;" is sufficient.

-- KAS

> real  0m2.293s
> user  0m2.275s
> sys   0m0.013s
>
> real  0m2.096s
> user  0m2.074s
> sys   0m0.014s

Nice :)
I'm looking forward nari-san's responce.

Issue #5033 has been updated by Narihiro Nakamura.


Hi,

Kurt  Stephens wrote:
> Minor GC improvement.
>
> Avoid recurring into gc_mark() when "goto again;" is sufficient.
>
> -- KAS

Nice try!

I read your patch.
In some program, GC is improved.

$ cat r.rb
GC::Profiler.enable
x = ["s"]
10_000_000.times do
  x[0] = x.dup
end
p GC::Profiler.total_time

origin: 0.28999999999999976
KAS's patch: 0.22999999999999993

I will accept this patch if GC performance is decrased in other 
programs.
----------------------------------------
Feature #5033: PATCH: 1.9: gc_mark_children: Avoid gc_mark() tail 
recursion, use goto again.
http://redmine.ruby-lang.org/issues/5033

Author: Kurt  Stephens
Status: Assigned
Priority: Normal
Assignee: Narihiro Nakamura
Category: core
Target version: 1.9.x


Minor GC improvement.

Avoid recurring into gc_mark() when "goto again;" is sufficient.

-- KAS

Issue #5033 has been updated by Kurt  Stephens.


There will be improvements for programs that have large numbers of 
Rational and Complex numbers.  If someone has a suitable benchmark 
please let me know.  Otherwise, I'll write something simple.
----------------------------------------
Feature #5033: PATCH: 1.9: gc_mark_children: Avoid gc_mark() tail 
recursion, use goto again.
http://redmine.ruby-lang.org/issues/5033

Author: Kurt  Stephens
Status: Assigned
Priority: Normal
Assignee: Narihiro Nakamura
Category: core
Target version: 1.9.x


Minor GC improvement.

Avoid recurring into gc_mark() when "goto again;" is sufficient.

-- KAS

Issue #5033 has been updated by authorNari (Narihiro Nakamura).

Status changed from Assigned to Closed
% Done changed from 0 to 100

I've committed part of your patch in r37088. Thanks!
----------------------------------------
Feature #5033: PATCH: 1.9: gc_mark_children: Avoid gc_mark() tail 
recursion, use goto again.
https://bugs.ruby-lang.org/issues/5033#change-30048

Author: kstephens (Kurt  Stephens)
Status: Closed
Priority: Normal
Assignee: authorNari (Narihiro Nakamura)
Category: core
Target version: 2.0.0


Minor GC improvement.

Avoid recurring into gc_mark() when "goto again;" is sufficient.

-- KAS