[ruby-core:61452] [ruby-trunk - Feature #9632] [Open] [PATCH 0/2] speedup IO#close with linked-list from ccan

[ruby-core:61452] [ruby-trunk - Feature #9632] [Open] [PATCH 0/2] speedup IO#close with linked-list from ccan

[normalperson]

Issue #9632 has been reported by Eric Wong.

----------------------------------------
Feature #9632: [PATCH 0/2] speedup IO#close with linked-list from ccan
https://bugs.ruby-lang.org/issues/9632

* Author: Eric Wong
* Status: Open
* Priority: Normal
* Assignee: Koichi Sasada
* Category: core
* Target version: current: 2.2.0
----------------------------------------
This imports the ccan linked-list (BSD-MIT licensed version of the Linux kernel
linked list).  I cut out some of the unused str* code (only for debugging),
but it's still a big import of new code.  Modifications to existing code is
minimal, and it makes the living_threads iteration functions simpler.

The improvement is great, and there may be future places where we could
use a doubly linked list.

= vm->living_threads:

* before: st hash table had extra malloc overhead, and slow iteration due
to bad cache locality

* after: guaranteed O(1) insert/remove performance (branchless!)
iteration is still O(n), but performance is improved in IO#close
due to less pointer chasing


= IO#close: further improvement with second linked list

* before: IO#close is linear based on number of living threads
* after: IO#close is linear based on number of waiting threads

No extra malloc is needed (only 2 new pointers in existing structs)
for a secondary linked-list for waiting FDs.


I chose the ccan linked list over BSD <sys/queue.h> for two reasons:
1) insertion and removal are both branchless
2) locality is improved if a struct may be a member of multiple lists

git://80x24.org/ruby.git threads-list


---Files--------------------------------
0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch (68.1 KB)
0002-speedup-IO-close-with-many-living-threads.patch (2.86 KB)


-- 
http://bugs.ruby-lang.org/

[ruby-core:61593] Re: [ruby-trunk - Feature #9632] [Open] [PATCH 0/2] speedup IO#close with linked-list from ccan

[Eric Wong]

normalperson@yhbt.net wrote:
> 0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch (68.1 KB)

I'll de-duplicate the CC0 declaration files if allowed to commit this.
The original had symlinks, but I assume symlinks are not allowed in this
source tree for portability.

I really like the Linux-kernel-style of linked-list.

[ruby-core:61595] [ruby-trunk - Feature #9632] [PATCH 0/2] speedup IO#close with linked-list from ccan

[normalperson]

Issue #9632 has been updated by Eric Wong.


 normalperson@yhbt.net wrote:
 > 0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch (68.1 KB)
 
 I'll de-duplicate the CC0 declaration files if allowed to commit this.
 The original had symlinks, but I assume symlinks are not allowed in this
 source tree for portability.
 
 I really like the Linux-kernel-style of linked-list.

----------------------------------------
Feature #9632: [PATCH 0/2] speedup IO#close with linked-list from ccan
https://bugs.ruby-lang.org/issues/9632#change-45872

* Author: Eric Wong
* Status: Open
* Priority: Normal
* Assignee: Koichi Sasada
* Category: core
* Target version: current: 2.2.0
----------------------------------------
This imports the ccan linked-list (BSD-MIT licensed version of the Linux kernel
linked list).  I cut out some of the unused str* code (only for debugging),
but it's still a big import of new code.  Modifications to existing code is
minimal, and it makes the living_threads iteration functions simpler.

The improvement is great, and there may be future places where we could
use a doubly linked list.

= vm->living_threads:

* before: st hash table had extra malloc overhead, and slow iteration due
to bad cache locality

* after: guaranteed O(1) insert/remove performance (branchless!)
iteration is still O(n), but performance is improved in IO#close
due to less pointer chasing


= IO#close: further improvement with second linked list

* before: IO#close is linear based on number of living threads
* after: IO#close is linear based on number of waiting threads

No extra malloc is needed (only 2 new pointers in existing structs)
for a secondary linked-list for waiting FDs.


I chose the ccan linked list over BSD <sys/queue.h> for two reasons:
1) insertion and removal are both branchless
2) locality is improved if a struct may be a member of multiple lists

git://80x24.org/ruby.git threads-list


---Files--------------------------------
0002-speedup-IO-close-with-many-living-threads.patch (2.86 KB)
0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch (68.1 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:61759] Re: [ruby-trunk - Feature #9632] [Open] [PATCH 0/2] speedup IO#close with linked-list from ccan

[Eric Wong]

Eric Wong <normalperson@yhbt.net> wrote:
> normalperson@yhbt.net wrote:
> > 0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch (68.1 KB)
> 
> I'll de-duplicate the CC0 declaration files if allowed to commit this.
> The original had symlinks, but I assume symlinks are not allowed in this
> source tree for portability.

Updated 0001 patch with deduplicated license files:
	http://bogomips.org/ruby.git/patch?id=b5401cdc6f72

I also renamed CCAN_INCLUDES to CCAN_LIST_INCLUDES in common.mk; in case
we import other modules from ccan[1].

[1] - http://ccodearchive.net/

[ruby-core:61760] [ruby-trunk - Feature #9632] [PATCH 0/2] speedup IO#close with linked-list from ccan

[normalperson]

Issue #9632 has been updated by Eric Wong.


 Eric Wong <normalperson@yhbt.net> wrote:
 > normalperson@yhbt.net wrote:
 > > 0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch (68.1 KB)
 > 
 > I'll de-duplicate the CC0 declaration files if allowed to commit this.
 > The original had symlinks, but I assume symlinks are not allowed in this
 > source tree for portability.
 
 Updated 0001 patch with deduplicated license files:
 	http://bogomips.org/ruby.git/patch?id=b5401cdc6f72
 
 I also renamed CCAN_INCLUDES to CCAN_LIST_INCLUDES in common.mk; in case
 we import other modules from ccan[1].
 
 [1] - http://ccodearchive.net/

----------------------------------------
Feature #9632: [PATCH 0/2] speedup IO#close with linked-list from ccan
https://bugs.ruby-lang.org/issues/9632#change-45994

* Author: Eric Wong
* Status: Open
* Priority: Normal
* Assignee: Koichi Sasada
* Category: core
* Target version: current: 2.2.0
----------------------------------------
This imports the ccan linked-list (BSD-MIT licensed version of the Linux kernel
linked list).  I cut out some of the unused str* code (only for debugging),
but it's still a big import of new code.  Modifications to existing code is
minimal, and it makes the living_threads iteration functions simpler.

The improvement is great, and there may be future places where we could
use a doubly linked list.

= vm->living_threads:

* before: st hash table had extra malloc overhead, and slow iteration due
to bad cache locality

* after: guaranteed O(1) insert/remove performance (branchless!)
iteration is still O(n), but performance is improved in IO#close
due to less pointer chasing


= IO#close: further improvement with second linked list

* before: IO#close is linear based on number of living threads
* after: IO#close is linear based on number of waiting threads

No extra malloc is needed (only 2 new pointers in existing structs)
for a secondary linked-list for waiting FDs.


I chose the ccan linked list over BSD <sys/queue.h> for two reasons:
1) insertion and removal are both branchless
2) locality is improved if a struct may be a member of multiple lists

git://80x24.org/ruby.git threads-list


---Files--------------------------------
0002-speedup-IO-close-with-many-living-threads.patch (2.86 KB)
0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch (68.1 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:61870] Re: [ruby-trunk - Feature #9632] [PATCH 0/2] speedup IO#close with linked-list from ccan

[Eric Wong]

normalperson@yhbt.net wrote:
>  Updated 0001 patch with deduplicated license files:
>  	http://bogomips.org/ruby.git/patch?id=b5401cdc6f72

Any comment?  My main concern is it's a large import of new code;
but it is also highly reusable.  I'll commit in 2-4 weeks if no response.
The 0002 patch can wait longer.

[ruby-core:61871] [ruby-trunk - Feature #9632] [PATCH 0/2] speedup IO#close with linked-list from ccan

[normalperson]

Issue #9632 has been updated by Eric Wong.


 normalperson@yhbt.net wrote:
 >  Updated 0001 patch with deduplicated license files:
 >  	http://bogomips.org/ruby.git/patch?id=b5401cdc6f72
 
 Any comment?  My main concern is it's a large import of new code;
 but it is also highly reusable.  I'll commit in 2-4 weeks if no response.
 The 0002 patch can wait longer.

----------------------------------------
Feature #9632: [PATCH 0/2] speedup IO#close with linked-list from ccan
https://bugs.ruby-lang.org/issues/9632#change-46087

* Author: Eric Wong
* Status: Open
* Priority: Normal
* Assignee: Koichi Sasada
* Category: core
* Target version: current: 2.2.0
----------------------------------------
This imports the ccan linked-list (BSD-MIT licensed version of the Linux kernel
linked list).  I cut out some of the unused str* code (only for debugging),
but it's still a big import of new code.  Modifications to existing code is
minimal, and it makes the living_threads iteration functions simpler.

The improvement is great, and there may be future places where we could
use a doubly linked list.

= vm->living_threads:

* before: st hash table had extra malloc overhead, and slow iteration due
to bad cache locality

* after: guaranteed O(1) insert/remove performance (branchless!)
iteration is still O(n), but performance is improved in IO#close
due to less pointer chasing


= IO#close: further improvement with second linked list

* before: IO#close is linear based on number of living threads
* after: IO#close is linear based on number of waiting threads

No extra malloc is needed (only 2 new pointers in existing structs)
for a secondary linked-list for waiting FDs.


I chose the ccan linked list over BSD <sys/queue.h> for two reasons:
1) insertion and removal are both branchless
2) locality is improved if a struct may be a member of multiple lists

git://80x24.org/ruby.git threads-list


---Files--------------------------------
0002-speedup-IO-close-with-many-living-threads.patch (2.86 KB)
0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch (68.1 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:62519] Re: [ruby-trunk - Feature #9632] [PATCH 0/2] speedup IO#close with linked-list from ccan

[Eric Wong]

Eric Wong <normalperson@yhbt.net> wrote:
> Any comment?  My main concern is it's a large import of new code;
> but it is also highly reusable.  I'll commit in 2-4 weeks if no response.
> The 0002 patch can wait longer.

Committed as r45913.  Hopefully nothing breaks, I tested extensively
on my "production" server.  Sorry for the delay, was busy.

[ruby-core:62520] [ruby-trunk - Feature #9632] [PATCH 0/2] speedup IO#close with linked-list from ccan

[normalperson]

Issue #9632 has been updated by Eric Wong.


 Eric Wong <normalperson@yhbt.net> wrote:
 > Any comment?  My main concern is it's a large import of new code;
 > but it is also highly reusable.  I'll commit in 2-4 weeks if no response.
 > The 0002 patch can wait longer.
 
 Committed as r45913.  Hopefully nothing breaks, I tested extensively
 on my "production" server.  Sorry for the delay, was busy.

----------------------------------------
Feature #9632: [PATCH 0/2] speedup IO#close with linked-list from ccan
https://bugs.ruby-lang.org/issues/9632#change-46679

* Author: Eric Wong
* Status: Open
* Priority: Normal
* Assignee: Koichi Sasada
* Category: core
* Target version: current: 2.2.0
----------------------------------------
This imports the ccan linked-list (BSD-MIT licensed version of the Linux kernel
linked list).  I cut out some of the unused str* code (only for debugging),
but it's still a big import of new code.  Modifications to existing code is
minimal, and it makes the living_threads iteration functions simpler.

The improvement is great, and there may be future places where we could
use a doubly linked list.

= vm->living_threads:

* before: st hash table had extra malloc overhead, and slow iteration due
to bad cache locality

* after: guaranteed O(1) insert/remove performance (branchless!)
iteration is still O(n), but performance is improved in IO#close
due to less pointer chasing


= IO#close: further improvement with second linked list

* before: IO#close is linear based on number of living threads
* after: IO#close is linear based on number of waiting threads

No extra malloc is needed (only 2 new pointers in existing structs)
for a secondary linked-list for waiting FDs.


I chose the ccan linked list over BSD <sys/queue.h> for two reasons:
1) insertion and removal are both branchless
2) locality is improved if a struct may be a member of multiple lists

git://80x24.org/ruby.git threads-list


---Files--------------------------------
0002-speedup-IO-close-with-many-living-threads.patch (2.86 KB)
0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch (68.1 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:62523] [ruby-trunk - Feature #9632] [PATCH 0/2] speedup IO#close with linked-list from ccan

[ko1]

Issue #9632 has been updated by Koichi Sasada.


Sorry for late response.

Just curious (I'm not against of this change).

1. How performance improved?
2. Should we modify ccan/* files? Or should we sync with originals?
3. What mean the name "CCAN"?


----------------------------------------
Feature #9632: [PATCH 0/2] speedup IO#close with linked-list from ccan
https://bugs.ruby-lang.org/issues/9632#change-46681

* Author: Eric Wong
* Status: Open
* Priority: Normal
* Assignee: Koichi Sasada
* Category: core
* Target version: current: 2.2.0
----------------------------------------
This imports the ccan linked-list (BSD-MIT licensed version of the Linux kernel
linked list).  I cut out some of the unused str* code (only for debugging),
but it's still a big import of new code.  Modifications to existing code is
minimal, and it makes the living_threads iteration functions simpler.

The improvement is great, and there may be future places where we could
use a doubly linked list.

= vm->living_threads:

* before: st hash table had extra malloc overhead, and slow iteration due
to bad cache locality

* after: guaranteed O(1) insert/remove performance (branchless!)
iteration is still O(n), but performance is improved in IO#close
due to less pointer chasing


= IO#close: further improvement with second linked list

* before: IO#close is linear based on number of living threads
* after: IO#close is linear based on number of waiting threads

No extra malloc is needed (only 2 new pointers in existing structs)
for a secondary linked-list for waiting FDs.


I chose the ccan linked list over BSD <sys/queue.h> for two reasons:
1) insertion and removal are both branchless
2) locality is improved if a struct may be a member of multiple lists

git://80x24.org/ruby.git threads-list


---Files--------------------------------
0002-speedup-IO-close-with-many-living-threads.patch (2.86 KB)
0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch (68.1 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:62524] [ruby-trunk - Feature #9632] [PATCH 0/2] speedup IO#close with linked-list from ccan

[ko1]

Issue #9632 has been updated by Koichi Sasada.


4. Should we use it on compile.c?

----------------------------------------
Feature #9632: [PATCH 0/2] speedup IO#close with linked-list from ccan
https://bugs.ruby-lang.org/issues/9632#change-46682

* Author: Eric Wong
* Status: Open
* Priority: Normal
* Assignee: Koichi Sasada
* Category: core
* Target version: current: 2.2.0
----------------------------------------
This imports the ccan linked-list (BSD-MIT licensed version of the Linux kernel
linked list).  I cut out some of the unused str* code (only for debugging),
but it's still a big import of new code.  Modifications to existing code is
minimal, and it makes the living_threads iteration functions simpler.

The improvement is great, and there may be future places where we could
use a doubly linked list.

= vm->living_threads:

* before: st hash table had extra malloc overhead, and slow iteration due
to bad cache locality

* after: guaranteed O(1) insert/remove performance (branchless!)
iteration is still O(n), but performance is improved in IO#close
due to less pointer chasing


= IO#close: further improvement with second linked list

* before: IO#close is linear based on number of living threads
* after: IO#close is linear based on number of waiting threads

No extra malloc is needed (only 2 new pointers in existing structs)
for a secondary linked-list for waiting FDs.


I chose the ccan linked list over BSD <sys/queue.h> for two reasons:
1) insertion and removal are both branchless
2) locality is improved if a struct may be a member of multiple lists

git://80x24.org/ruby.git threads-list


---Files--------------------------------
0002-speedup-IO-close-with-many-living-threads.patch (2.86 KB)
0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch (68.1 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:62525] Re: [ruby-trunk - Feature #9632] [PATCH 0/2] speedup IO#close with linked-list from ccan

[Eric Wong]

ko1@atdot.net wrote:
> 1. How performance improved?

There is less pointer chasing for iteration:

Before: st_table_entry->rb_thread_t->st_table_entry->rb_thread_t ...
 After: rb_thread->rb_thread ...

This is made possible by the container_of macro.

I plan to use container_of in method/constant/symbol table, too
(ihash in Feature #9614).

> 2. Should we modify ccan/* files? Or should we sync with originals?

I probably best to sync with originals.  I removed parts of
ccan/str/str.h we are not using, but we can use more of str.h later.
I may also put ihash in CCAN so other projects may use it easily.
But I am not sure about the name "ihash".

> 3. What mean the name "CCAN"?

Comprehensive C Archive Network - ccodearchive.net

> 4. Should we use it on compile.c?

Maybe.  I do not know compile.c well enough...
If we can reduce allocations and pointer chasing without regressions,
we should use it.

[ruby-core:62526] [ruby-trunk - Feature #9632] [PATCH 0/2] speedup IO#close with linked-list from ccan

[normalperson]

Issue #9632 has been updated by Eric Wong.


 ko1@atdot.net wrote:
 > 1. How performance improved?
 
 There is less pointer chasing for iteration:
 
 Before: st_table_entry->rb_thread_t->st_table_entry->rb_thread_t ...
  After: rb_thread->rb_thread ...
 
 This is made possible by the container_of macro.
 
 I plan to use container_of in method/constant/symbol table, too
 (ihash in Feature #9614).
 
 > 2. Should we modify ccan/* files? Or should we sync with originals?
 
 I probably best to sync with originals.  I removed parts of
 ccan/str/str.h we are not using, but we can use more of str.h later.
 I may also put ihash in CCAN so other projects may use it easily.
 But I am not sure about the name "ihash".
 
 > 3. What mean the name "CCAN"?
 
 Comprehensive C Archive Network - ccodearchive.net
 
 > 4. Should we use it on compile.c?
 
 Maybe.  I do not know compile.c well enough...
 If we can reduce allocations and pointer chasing without regressions,
 we should use it.

----------------------------------------
Feature #9632: [PATCH 0/2] speedup IO#close with linked-list from ccan
https://bugs.ruby-lang.org/issues/9632#change-46683

* Author: Eric Wong
* Status: Open
* Priority: Normal
* Assignee: Koichi Sasada
* Category: core
* Target version: current: 2.2.0
----------------------------------------
This imports the ccan linked-list (BSD-MIT licensed version of the Linux kernel
linked list).  I cut out some of the unused str* code (only for debugging),
but it's still a big import of new code.  Modifications to existing code is
minimal, and it makes the living_threads iteration functions simpler.

The improvement is great, and there may be future places where we could
use a doubly linked list.

= vm->living_threads:

* before: st hash table had extra malloc overhead, and slow iteration due
to bad cache locality

* after: guaranteed O(1) insert/remove performance (branchless!)
iteration is still O(n), but performance is improved in IO#close
due to less pointer chasing


= IO#close: further improvement with second linked list

* before: IO#close is linear based on number of living threads
* after: IO#close is linear based on number of waiting threads

No extra malloc is needed (only 2 new pointers in existing structs)
for a secondary linked-list for waiting FDs.


I chose the ccan linked list over BSD <sys/queue.h> for two reasons:
1) insertion and removal are both branchless
2) locality is improved if a struct may be a member of multiple lists

git://80x24.org/ruby.git threads-list


---Files--------------------------------
0002-speedup-IO-close-with-many-living-threads.patch (2.86 KB)
0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch (68.1 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:62527] Re: [ruby-trunk - Feature #9632] [PATCH 0/2] speedup IO#close with linked-list from ccan

[Eric Wong]

Eric Wong <normalperson@yhbt.net> wrote:
> Before: st_table_entry->rb_thread_t->st_table_entry->rb_thread_t ...

Sorry, bad picture for Before, this is more accurate:

	st_table_entry -> st_table_entry -> st_table_entry
	    |                 |                 |
	    V                 V                 V
	rb_thread_t       rb_thread_t       rb_thread_t

[ruby-core:62528] [ruby-trunk - Feature #9632] [PATCH 0/2] speedup IO#close with linked-list from ccan

[normalperson]

Issue #9632 has been updated by Eric Wong.


 Eric Wong <normalperson@yhbt.net> wrote:
 > Before: st_table_entry->rb_thread_t->st_table_entry->rb_thread_t ...
 
 Sorry, bad picture for Before, this is more accurate:
 
 	st_table_entry -> st_table_entry -> st_table_entry
 	    |                 |                 |
 	    V                 V                 V
 	rb_thread_t       rb_thread_t       rb_thread_t

----------------------------------------
Feature #9632: [PATCH 0/2] speedup IO#close with linked-list from ccan
https://bugs.ruby-lang.org/issues/9632#change-46684

* Author: Eric Wong
* Status: Open
* Priority: Normal
* Assignee: Koichi Sasada
* Category: core
* Target version: current: 2.2.0
----------------------------------------
This imports the ccan linked-list (BSD-MIT licensed version of the Linux kernel
linked list).  I cut out some of the unused str* code (only for debugging),
but it's still a big import of new code.  Modifications to existing code is
minimal, and it makes the living_threads iteration functions simpler.

The improvement is great, and there may be future places where we could
use a doubly linked list.

= vm->living_threads:

* before: st hash table had extra malloc overhead, and slow iteration due
to bad cache locality

* after: guaranteed O(1) insert/remove performance (branchless!)
iteration is still O(n), but performance is improved in IO#close
due to less pointer chasing


= IO#close: further improvement with second linked list

* before: IO#close is linear based on number of living threads
* after: IO#close is linear based on number of waiting threads

No extra malloc is needed (only 2 new pointers in existing structs)
for a secondary linked-list for waiting FDs.


I chose the ccan linked list over BSD <sys/queue.h> for two reasons:
1) insertion and removal are both branchless
2) locality is improved if a struct may be a member of multiple lists

git://80x24.org/ruby.git threads-list


---Files--------------------------------
0002-speedup-IO-close-with-many-living-threads.patch (2.86 KB)
0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch (68.1 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:62557] [ruby-trunk - Feature #9632] [PATCH 0/2] speedup IO#close with linked-list from ccan

[akr]

Issue #9632 has been updated by Akira Tanaka.


 2014-05-11 8:50 GMT+09:00 Eric Wong <normalperson@yhbt.net>:
 > Eric Wong <normalperson@yhbt.net> wrote:
 >> Any comment?  My main concern is it's a large import of new code;
 >> but it is also highly reusable.  I'll commit in 2-4 weeks if no response.
 >> The 0002 patch can wait longer.
 >
 > Committed as r45913.  Hopefully nothing breaks, I tested extensively
 > on my "production" server.  Sorry for the delay, was busy.
 
 I found that doxygen produces many warnings in ccan/ directory.
 http://www.rubyist.net/~akr/chkbuild/debian/ruby-trunk/log/20140510T235500Z.diff.html.gz
 
 It seems the comments in ccan/ directory is not doxygen-compatible.
 
 Anyone use doxygen?
 If no one use it, we can drop doxygen support.
 (It makes the CI faster.)
 -- 
 Tanaka Akira

----------------------------------------
Feature #9632: [PATCH 0/2] speedup IO#close with linked-list from ccan
https://bugs.ruby-lang.org/issues/9632#change-46708

* Author: Eric Wong
* Status: Open
* Priority: Normal
* Assignee: Koichi Sasada
* Category: core
* Target version: current: 2.2.0
----------------------------------------
This imports the ccan linked-list (BSD-MIT licensed version of the Linux kernel
linked list).  I cut out some of the unused str* code (only for debugging),
but it's still a big import of new code.  Modifications to existing code is
minimal, and it makes the living_threads iteration functions simpler.

The improvement is great, and there may be future places where we could
use a doubly linked list.

= vm->living_threads:

* before: st hash table had extra malloc overhead, and slow iteration due
to bad cache locality

* after: guaranteed O(1) insert/remove performance (branchless!)
iteration is still O(n), but performance is improved in IO#close
due to less pointer chasing


= IO#close: further improvement with second linked list

* before: IO#close is linear based on number of living threads
* after: IO#close is linear based on number of waiting threads

No extra malloc is needed (only 2 new pointers in existing structs)
for a secondary linked-list for waiting FDs.


I chose the ccan linked list over BSD <sys/queue.h> for two reasons:
1) insertion and removal are both branchless
2) locality is improved if a struct may be a member of multiple lists

git://80x24.org/ruby.git threads-list


---Files--------------------------------
0002-speedup-IO-close-with-many-living-threads.patch (2.86 KB)
0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch (68.1 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:62560] [ruby-trunk - Feature #9632] [PATCH 0/2] speedup IO#close with linked-list from ccan

[normalperson]

Issue #9632 has been updated by Eric Wong.


 Tanaka Akira <akr@fsij.org> wrote:
 > I found that doxygen produces many warnings in ccan/ directory.
 > http://www.rubyist.net/~akr/chkbuild/debian/ruby-trunk/log/20140510T235500Z.diff.html.gz
 > 
 > It seems the comments in ccan/ directory is not doxygen-compatible.
 
 Sorry about that.
 
 > Anyone use doxygen?
 > If no one use it, we can drop doxygen support.
 > (It makes the CI faster.)
 
 I do not use it.
 
 We may also fix the comments to be doxygen-compatible and send patches
 upstream to ccan.  But if nobody uses doxygen, we save time by dropping
 it.

----------------------------------------
Feature #9632: [PATCH 0/2] speedup IO#close with linked-list from ccan
https://bugs.ruby-lang.org/issues/9632#change-46709

* Author: Eric Wong
* Status: Open
* Priority: Normal
* Assignee: Koichi Sasada
* Category: core
* Target version: current: 2.2.0
----------------------------------------
This imports the ccan linked-list (BSD-MIT licensed version of the Linux kernel
linked list).  I cut out some of the unused str* code (only for debugging),
but it's still a big import of new code.  Modifications to existing code is
minimal, and it makes the living_threads iteration functions simpler.

The improvement is great, and there may be future places where we could
use a doubly linked list.

= vm->living_threads:

* before: st hash table had extra malloc overhead, and slow iteration due
to bad cache locality

* after: guaranteed O(1) insert/remove performance (branchless!)
iteration is still O(n), but performance is improved in IO#close
due to less pointer chasing


= IO#close: further improvement with second linked list

* before: IO#close is linear based on number of living threads
* after: IO#close is linear based on number of waiting threads

No extra malloc is needed (only 2 new pointers in existing structs)
for a secondary linked-list for waiting FDs.


I chose the ccan linked list over BSD <sys/queue.h> for two reasons:
1) insertion and removal are both branchless
2) locality is improved if a struct may be a member of multiple lists

git://80x24.org/ruby.git threads-list


---Files--------------------------------
0002-speedup-IO-close-with-many-living-threads.patch (2.86 KB)
0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch (68.1 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:62561] [ruby-trunk - Feature #9632] [PATCH 0/2] speedup IO#close with linked-list from ccan

[nobu]

Issue #9632 has been updated by Nobuyoshi Nakada.


 (2014/05/13 16:29), Eric Wong wrote:
 > Tanaka Akira <akr@fsij.org> wrote:
 >> Anyone use doxygen?
 >> If no one use it, we can drop doxygen support.
 >> (It makes the CI faster.)
 > 
 > I do not use it.
 
 I don't use it too (it's too time consuming)
 
 > We may also fix the comments to be doxygen-compatible and send patches
 > upstream to ccan.  But if nobody uses doxygen, we save time by dropping
 > it.
 
 Or adding ccan to EXCLUDE in template/Doxyfile.tmpl.

----------------------------------------
Feature #9632: [PATCH 0/2] speedup IO#close with linked-list from ccan
https://bugs.ruby-lang.org/issues/9632#change-46710

* Author: Eric Wong
* Status: Open
* Priority: Normal
* Assignee: Koichi Sasada
* Category: core
* Target version: current: 2.2.0
----------------------------------------
This imports the ccan linked-list (BSD-MIT licensed version of the Linux kernel
linked list).  I cut out some of the unused str* code (only for debugging),
but it's still a big import of new code.  Modifications to existing code is
minimal, and it makes the living_threads iteration functions simpler.

The improvement is great, and there may be future places where we could
use a doubly linked list.

= vm->living_threads:

* before: st hash table had extra malloc overhead, and slow iteration due
to bad cache locality

* after: guaranteed O(1) insert/remove performance (branchless!)
iteration is still O(n), but performance is improved in IO#close
due to less pointer chasing


= IO#close: further improvement with second linked list

* before: IO#close is linear based on number of living threads
* after: IO#close is linear based on number of waiting threads

No extra malloc is needed (only 2 new pointers in existing structs)
for a secondary linked-list for waiting FDs.


I chose the ccan linked list over BSD <sys/queue.h> for two reasons:
1) insertion and removal are both branchless
2) locality is improved if a struct may be a member of multiple lists

git://80x24.org/ruby.git threads-list


---Files--------------------------------
0002-speedup-IO-close-with-many-living-threads.patch (2.86 KB)
0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch (68.1 KB)


-- 
https://bugs.ruby-lang.org/

[ruby-core:65022] Re: [ruby-trunk - Feature #9632] [PATCH 0/2] speedup IO#close with linked-list from ccan

[Eric Wong]

ko1@atdot.net wrote:
> 4. Should we use it on compile.c?

Yes, and probably gc.c, too.  I think it would help improve readability
and remove some branches in our current code.

I have submitted patches for list_add_after, list_add_before and
list_swap functions:
https://lists.ozlabs.org/pipermail/ccan/2014-September/thread.html

I think this will be next year for Ruby 2.3.

[ruby-core:65023] [ruby-trunk - Feature #9632] [PATCH 0/2] speedup IO#close with linked-list from ccan

[normalperson]

Issue #9632 has been updated by Eric Wong.


 ko1@atdot.net wrote:
 > 4. Should we use it on compile.c?
 
 Yes, and probably gc.c, too.  I think it would help improve readability
 and remove some branches in our current code.
 
 I have submitted patches for list_add_after, list_add_before and
 list_swap functions:
 https://lists.ozlabs.org/pipermail/ccan/2014-September/thread.html
 
 I think this will be next year for Ruby 2.3.

----------------------------------------
Feature #9632: [PATCH 0/2] speedup IO#close with linked-list from ccan
https://bugs.ruby-lang.org/issues/9632#change-48893

* Author: Eric Wong
* Status: Open
* Priority: Normal
* Assignee: Koichi Sasada
* Category: core
* Target version: current: 2.2.0
----------------------------------------
This imports the ccan linked-list (BSD-MIT licensed version of the Linux kernel
linked list).  I cut out some of the unused str* code (only for debugging),
but it's still a big import of new code.  Modifications to existing code is
minimal, and it makes the living_threads iteration functions simpler.

The improvement is great, and there may be future places where we could
use a doubly linked list.

= vm->living_threads:

* before: st hash table had extra malloc overhead, and slow iteration due
to bad cache locality

* after: guaranteed O(1) insert/remove performance (branchless!)
iteration is still O(n), but performance is improved in IO#close
due to less pointer chasing


= IO#close: further improvement with second linked list

* before: IO#close is linear based on number of living threads
* after: IO#close is linear based on number of waiting threads

No extra malloc is needed (only 2 new pointers in existing structs)
for a secondary linked-list for waiting FDs.


I chose the ccan linked list over BSD <sys/queue.h> for two reasons:
1) insertion and removal are both branchless
2) locality is improved if a struct may be a member of multiple lists

git://80x24.org/ruby.git threads-list


---Files--------------------------------
0002-speedup-IO-close-with-many-living-threads.patch (2.86 KB)
0001-doubly-linked-list-from-ccan-to-manage-vm-living_thr.patch (68.1 KB)


-- 
https://bugs.ruby-lang.org/