Re: GSOC Proposal

[Richard Biener <rguenther@suse.de>]

On April 5, 2019 6:11:15 PM GMT+02:00, nick <xerofoify@gmail.com> wrote:
>
>
>On 2019-04-05 6:25 a.m., Richard Biener wrote:
>> On Wed, 3 Apr 2019, nick wrote:
>> 
>>>
>>>
>>> On 2019-04-03 7:30 a.m., Richard Biener wrote:
>>>> On Mon, 1 Apr 2019, nick wrote:
>>>>
>>>>>
>>>>>
>>>>> On 2019-04-01 9:47 a.m., Richard Biener wrote:
>>>>>> On Mon, 1 Apr 2019, nick wrote:
>>>>>>
>>>>>>> Well I'm talking about the shared roots of this garbage
>collector core state 
>>>>>>> data structure or just struct ggc_root_tab.
>>>>>>>
>>>>>>> But also this seems that this to be no longer shared globally if
>I'm not mistaken 
>>>>>>> or this:
>>>>>>> static vec<const_ggc_root_tab_t> extra_root_vec;
>>>>>>>
>>>>>>> Not sure after reading the code which is a bigger deal through
>so I wrote
>>>>>>> my proposal not just asking which is a better issue for not
>being thread
>>>>>>> safe. Sorry about that.
>>>>>>>
>>>>>>> As for the second question injection seems to not be the issue
>or outside
>>>>>>> callers but just internal so phase 3 or step 3 would now be:
>>>>>>> Find internal callers or users of x where x is one of the above
>rather
>>>>>>> than injecting outside callers. Which answers my second question
>about
>>>>>>> external callers being a issue still.
>>>>>>>
>>>>>>> Let me know which  of the two is a better issue:
>>>>>>> 1. struct ggc_root_tabs being shared
>>>>>>> 2.static vec<const_ggc_root_tab_t> extra_root_vec; as a shared
>heap or
>>>>>>> vector of root nodes for each type of allocation
>>>>>>>
>>>>>>> and I will gladly rewrite my proposal sections for that
>>>>>>> as needs to be reedited.
>>>>>>
>>>>>> I don't think working on the garbage collector as a separate
>>>>>> GSoC project is useful at this point.  Doing locking around
>>>>>> allocation seems like a good short-term solution and if that
>>>>>> turns out to be a performance issue for the threaded part
>>>>>> using per-thread freelists is likely an easy to deploy
>>>>>> solution.
>>>>>>
>>>>>> Richard.
>>>>>>
>>>>> I agree but we were discussing this:
>>>>> Or maybe a project to be more
>>>>> explicit about regions of the code that assume that the garbage-
>>>>> collector can't run within them?[3] (since the GC is state that
>would
>>>>> be shared by the threads).
>>>>
>>>> The process of collecting garbage is not the only issue (and that
>>>> very issue is easiest mitigated by collecting only at specific
>>>> points - which is what we do - and have those be serializing
>points).
>>>> The main issue is the underlying memory allocator (GCC uses memory
>>>> that is garbage collected plus regular heap memory).
>>>>
>>>>> In addition I moved my paper back to our discussion about garbage
>collector
>>>>> state with outside callers.Seems we really need to do something
>about
>>>>> my wording as the idea of my project in a nutshell was to figure
>>>>> out how to mark shared state by callers and inject it into the
>>>>> garbage collector letting it known that the state was not shared
>between
>>>>> threads or shared. Seems that was on the GSoc page and in our
>discussions the issue
>>>>> is marking outside code for shared state. If that's correct then
>my
>>>>> wording of outside callers is incorrect it should have been shared
>>>>> state between threads on outside callers to the garbage collector.
>>>>> If the state is that in your wording above then great as I
>understand
>>>>> where we are going and will gladly change my wording.
>>>>
>>>> I'm still not sure what you are shooting at, the above sentences do
>>>> not make any sense to me.
>>>>
>>>>> Also freelists don't work here as the state is shared at the
>caller's 
>>>>> end which would need two major issues:
>>>>> 1. Locking on nodes of the 
>>>>> freelists when two threads allocate at the same thing which can be
>a 
>>>>> problem if the shared state is shared a lot
>>>>> 2. Locking allocation with 
>>>>> large numbers of callers can starve threads
>>>>
>>>> First of all allocating memory from the GC pool is not the main
>>>> work of GIMPLE passes so simply serializing at allocation time
>might
>>>> work out.  Second free lists of course do work.  What you'd do is
>>>> have a fast path in allocation using a thread-local "free list"
>>>> which you can allocate from without taking any lock.  Maybe I
>should
>>>> explain "free list" since that term doesn't make too much sense in
>>>> a garbage collector world.  What I'd do is when a client thread
>>>> asks for memory of size N allocate M objects of that size but put
>>>> M - 1 on the client thread local "free list" to be allocated
>lock-free
>>>> from for the next M - 1 calls.  Note that garbage collected memory
>>>> objects are only handed out in fixed chunks (powers of two plus
>>>> a few special sizes) so you'd have one "free list" per chunk size
>>>> per thread.
>>>>
>>>> The collection itself (mark & sweep) would be fully serialized
>still
>>>> (and not return to any threads local "free list").
>>>>
>>>> ggc_free'd objects _might_ go to the threads "free list"s (yeah, we
>>>> _do_ have ggc_free ...).
>>>>
>>>> As said, I don't see GC or the memory allocator as sth interesting
>>>> to work on for parallelization until the basic setup works and it
>>>> proves to be a bottleneck.
>>>>
>>>>> Seems that working on the garbage collector itself isn't the issue
>but 
>>>>> the callers as I just figured out as related to your state idea.
>Let me 
>>>>> know if that's correct and if the wording change I mentioned is
>fine 
>>>>> with you as that's the state it seems that needs to be changed.
>>>>> Nick 
>>>>
>>>> Richard.
>>>>
>>>
>>> That's fine and it's my fault for not understanding you better. I
>was aware 
>>> of the expand_functions_all being taken for passes.c. However it
>seems
>>> two other issues are these sets as related to threads:
>>> 1.finalize_compilation_unit
>>> 2.and the ipa set of pass functions
>>>
>>> If I'm understanding it correctly number 1 seems to be a early
>version of
>>> expand_all_functions for the GENERIC representation if that's the
>case
>>> it really should be fixed. Not sure which is a better issue as both
>>> seem to have issues either at the GENERIC level or GIMPLE level with
>shared
>>> state.
>>>
>>> Let me know if this is better as it seems now that I really think
>about 
>>> it GIMPLE or GENERIC functions in passes.c are the main issue. 
>>>
>>> Sorry for the misunderstanding and hopefully one of functions listed
>is better
>>> for moving forward with my proposal,
>> 
>> Sorry, but guessing at useful projects by skimming through GCC code
>> at this point isn't the way to go forward - this new "idea" lacks
>> both detail and understanding.  Please try to stick to one of the
>> suggested projects or do more thorough research in case you want
>> to work on a new project idea next year.
>> 
>> Thanks,
>> Richard.
>> 
>
>I was talking about cgraphunits.c and it seems that according to this:
>Parallelize compilation using threads. GCC currently has an awful lot
>of truly global state and even more per-pass global state which makes
>this somewhat hard. The idea is to avoid issues with global state as
>much as possible by partitioning the compilation pipeline in pieces
>that share as little global state as possible and ensure each thread
>only works in one of those partitions. The biggest roadblock will be
>the not thread-safe memory allocator of GCC garbage collector. The goal
>of this project is to have a compilation pipeline driven by a scheduler
>assigning functions to be optimized to the partitions in the pipeline.
>This project would be mentored by Richard Biener. Required skills
>include: C/C++, ability to analyze big complex code base,
>parallelization
>
>We are trying to create a rendering pipeline if I'm correct and it
>seems that the GENERIC level needs finalize_compilation_unit
>to be fixed like expand_all_functions at the GIMPLE. That's my point it
>still is within that project. Here is what I wrote
>as I figured out that it was shared state related to GENERIC passing to
>GIMPLE which is a bottleneck or would be in the 
>threaded pipeline.
>
>https://docs.google.com/document/d/1BKVeh62IpigsQYf_fJqkdu_js0EeGdKtXInkWZ-DtU0/edit

The pre- post-IPA parts cannot be easily parallelized and that includes GENERIC to GIMPLE translation. This is why the project should focus on the much easier post-IPA and pre-RTL parts of the compilation pipeline since there interaction between functions is minimal. 

Richard. 

>
>Nick