[prev in list] [next in list] [prev in thread] [next in thread] 

List:       ruby-core
Subject:    [ruby-core:68670] Introductions and GSoC Proposal
From:       William Woodruff <william () tuffbizz ! com>
Date:       2015-03-28 19:53:50
Message-ID: 551706CE.4010601 () tuffbizz ! com
[Download RAW message or body]

Hello everybody!

My name is William Woodruff. I'm a Google Summer of Code applicant,
and I'm excited to work on the MRI.

In particular, I'm very interested in implementing a type-switcher in
the Ruby runtime, something that can dynamically change the
representation of a program's data to better suit its characteristics.
I'm also looking forward to adding new data structures to the runtime
to make list and tree programming more efficient and native to MRI
itself.

For a more detailed list of ideas, I'm attaching my proposal
(proposal.txt) as a potential timeline (timeline.txt) for review.

If there are any developers who would be willing to mentor and advise me
through this process, I would be extremely grateful for any information
or advice they could give me.

I'm very open to new ideas, suggestions, and criticisms so please send
my way :).

Thanks,
William Woodruff (william@tuffbizz.com)

["proposal.txt" (text/plain)]

Hello,

My name is William Woodruff, and I'm applying to work on the Matz Ruby
Interpreter for Google's 2015 Summer of Code.

My email address is william@tuffbizz.com,

and my GitHub handle is @woodruffw, which I publish all of my open-source
projects under.

You can also find a copy of my resume at http://woodruffw.us/resume.pdf.

I'm a freshman majoring in Computer Science at the University of Maryland,
College Park, currently taking classes in systems programming.

I would like to tackle two ideas for the MRI: dynamically switching data
structures for performance and adding additional structures and implementations
to the Ruby standard library. I believe that I have the skills to accomplish
both of these goals, having taken a data structures course and having experience
with both Ruby and C.

For a structure switcher inside the MRI, I would like to do the following things:

    - Implement the structure switcher itself. The switcher could either act as
    a core component of the MRI, or as a parent of all data structures suited
    for a given task. In the latter case, the occurrence of conditions amenable
    to a structure change would be propagated from the children structures to
    the parent, which would manage the switch.
    
    - Add a rope structure that replaces standard character arrays for strings
    of significant length. This length could start at a constant, or be
    determined/modified at runtime depending on memory or speed constraints.
    This could make insertions and deletions on long strings O(1), instead of
    the current O(n). It would also decrease the chance of a malloc/OOM failure,
    as new insertions would not require contiguously allocated memory.
    
    Add a cuckoo hashing implementation to supplement the current st hash table
    implementation. This could allow for tables with higher load factors, and a
    sufficiently limber implementation could determine the number of hashing
    functions to use depending on the load required. In addition, cuckoo hashing
    has a worst-case indexing complexity of O(1), instead of the current O(n).
    Yet another alternative is hopscotch hash.

I would also like to add some new structures to the MRI:

    - Ruby programmers could benefit from the presence of various linked list
    structures, including singly- and doubly-linked lists. These could
    complement the Array class in providing the abstract functionality of a
    "List".

    Trees could also be added to the standard library in a number of forms,
    including unregulated, binary, and max/min heaps. These, in turn, can be
    used internally to improve the performance of various operations
    (most importantly searches).

Thank you for considering me and my proposal. I look forward to hearing from you.

William Woodruff

["timeline.txt" (text/plain)]

* May 25 - June 8 would be dedicated to learning the MRI's structure and
implementation. I need to understand Ruby's type system before I
modify/supplement it with a runtime type switcher. I would also use these two
weeks to research similar type-switching projects both inside and outside of
Ruby, to learn Ruby's coding style and community, and to set up an environment
for building the source tree.

* June 8 - 15 would be for planning the structure of the switching system. As I
mentioned in my proposal, the switcher could either be tightly coupled to the
interpreter/VM or more loosely via a hierarchy of abstract data types and
callbacks. Once a model is decided on, I would draft it as pseudocode.

* June 15 - 22 would be the beginning of actually implementing the switcher. I
would create a branch of the stable MRI tree, and start with individual ADTs
that would most benefit from switching (e.g. strings, tables).

* By the end of June 29, I would like to have a working skeleton form of the
switcher that builds and functions with at least one ADT (probably strings via
character array <-> rope switching).

* From June 29 to July 13, I would complete the switcher and add additional
swapable types to it (specifically hash table swapping). Included in this period
would be creating passing a series of rigorous benchmarks to ensure that
performance doesn't degrade during swaps or as a result of them. In addition,
I would create a suite of type and stress tests and use them during this period.

* By July 20 I would like to have the switcher fully available for MRI
developers and the greater Ruby community to test in a development build.

* From July 20 to August 3, I would add additional types to my MRI branch. These
types would not necessarily have to be involved in the type switcher,
but could simply be convenient types that Ruby currently lacks (like heaps,
general purpose trees, and linked lists).

* From August 3 to August 10 I would complete, and benchmark these additional
types. The ultimate goal would be to have near-native performance for simple
tree and list operations, and I think this could be accomplished with rigorous
implementation(s). From August 10 to 17 I would complete my testing of the new
types and provide them once again to the community for review before formally
requesting they be added to the mainline MRI.

* Finally, from August 17 to 24, I would work to get my contributions merged
into an official branch for eventual release with the MRI, and to alert other
Ruby implementations of the changes so that they could bring them in and apply
them.


[prev in list] [next in list] [prev in thread] [next in thread]