Project

General

Profile

Actions

Feature #9632

closed

[PATCH 0/2] speedup IO#close with linked-list from ccan

Added by normalperson (Eric Wong) about 8 years ago. Updated about 5 years ago.

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

Description

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

Actions

Also available in: Atom PDF