Improve Performance or Reduce Memory Usage in the Mono Compiler.

[GoogleCodeExporter]

In the Mono C# compiler, performance is tightly bound to memory usage.  
The less memory we use, the faster the compiler is.

The goal of this task is to reduce the memory usage used by the Mono C#
compiler.   A previous high-school student helped accelerate the Mono C#
compiler and eventually went to work for Google for the summers.

But as time has passed, the compiler has become chubbier and it could use a
number of passes to reduce its memory usage again (the last time we looked
at performance on it, it was two years ago).

The goal would be to reduce the memory consumption by 10% on bootstrapping
itself or in compiling any of the Mono libraires (mscolibr, System).

Original issue reported on code.google.com by miguel.d...@gmail.com on 22 Nov 2007 at 12:01

[GoogleCodeExporter]

This task should take anywhere between 5 and 10 days.

The fix should not break the compiler, so all the tests should continue to run.

Original comment by miguel.d...@gmail.com on 27 Nov 2007 at 10:13

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

I claim this Task

Original comment by benjamin...@gmail.com on 28 Nov 2007 at 11:12

[GoogleCodeExporter]

Original comment by shana.u...@gmail.com on 2 Dec 2007 at 10:41

• Changed state: Claimed
• Added labels: ClaimedBy-benjamin.s.berman

[GoogleCodeExporter]

For now I will withdraw from this issue, as I cannot meet the 10 day deadline. 
Anyone
else may claim this issue. In the meantime, I will continue my work and reclaim 
it if
I have met the criteria and if no one else has claimed the issue.

Thanks

Original comment by benjamin...@gmail.com on 7 Dec 2007 at 1:23

[GoogleCodeExporter]

That is fine.  I think this is a task that if multiple people want to attempt, 
we
will fork a new task for each to claim.  Thanks for letting us know!

Original comment by jpo...@gmail.com on 7 Dec 2007 at 3:15

• Changed state: Open
• Added labels: Performance
• Removed labels: ClaimedBy-benjamin.s.berman, performance

[GoogleCodeExporter]

I claim this task.

Original comment by AdT...@gmail.com on 18 Dec 2007 at 2:52

[GoogleCodeExporter]

Original comment by jpo...@gmail.com on 18 Dec 2007 at 2:54

• Changed state: Claimed
• Added labels: ClaimedBy-AdTsai

[GoogleCodeExporter]

After about a day of reading, I'm beginning to understand the basic structure 
of 
mcs, and how it works. Although, I've only been able to do some _very_ rough 
performance analysis; the fact that mcs itself runs under mono precludes the 
usage 
of proper profiling tools (at least, all the ones I've tried).

Because of the lack of profilers, all I've been able to garner so far from my 
limited trial-and-error testing is that a large portion of the total memory 
used by 
the program is allocated during code emission.

I've still got a very, very long way to go, so I was wondering if any of the 
developers knew of any potential allocation-heavy performance hotspots - 
because 
what I've got currently ("sometime during EmitCode()") isn't going to get me 
very 
far.

Original comment by AdT...@gmail.com on 19 Dec 2007 at 1:55

[GoogleCodeExporter]

Hi,

The name of the game here isn't reducing the peak memory consumption (eg, what 
you'd
see in ps aux), but rather reducing the number of allocations. There are two 
reasons
for this. First, high numbers of allocations often indicate places where an
inefficient algorithm is used. I always found that looking at the CPU time 
profiles
was difficult and that memory allocation was a better way to find these 
inefficient
spots. Secondly, the act of memory allocation is somewhat expensive itself, so 
even
if it doesn't point to a place where the algorithm can be changed, it's still 
useful
to reduce.

It's been a long time since I've done Mono profiling and there are probably 
some new
tools around. However, for mcs, I found that --profile was a pretty good tool 
on it's
own.

For getting started, your best bet is to run the MCS bootstrap with --profile 
enabled
(there should be a makefile target for this). Then skip down to the memory
allocations section.

- Ben

Original comment by ben.maurer on 19 Dec 2007 at 3:32

[GoogleCodeExporter]

Ah, thanks! I didn't know about the mono profiler, that should help alot!

I have some questions about the C# parser, it's in cs-parser.cs, but I have a 
feeling that I shouldn't be editing that file directly. I'm guessing that it's 
procedurally generated, so how would I go about editing the parser code, if I 
could?

Original comment by AdT...@gmail.com on 20 Dec 2007 at 4:37

[GoogleCodeExporter]

That's generated by the .jay file. There are two types of potential issues 
their.
Either you need to edit the inline c# code in the jay file, or there's some 
sort of
issue with the jay code itself and you need to modify the compiler.

Original comment by ben.maurer on 20 Dec 2007 at 5:16

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

I'm not entirely sure how to submit the changes - but the relevant code files 
are 
attached, along with a log of my changes.

When I started, the profiler reported 59333kb allocations while compiling 
itself - 
now it reports 54893kb, which is an 8.08% decrease in allocations. By my 
testing, 
this caused an approximate 5-6% decrease in compilation time. Not much, but I 
guess 
it's something.

Heh, the vast, vast majority of my time working on this was profiling and 
testing - 
only a few minutes was spent actually modifying code, the rest was spent trying 
to 
find what bottlenecks were available and finding ways to relieve them. I made 
only a 
few small changes here and there - but it translated into a reasonable 
reduction in 
memory. If the changes aren't satisfactory, just say so, and I'll continue to 
work 
on it.

Original comment by AdT...@gmail.com on 24 Dec 2007 at 5:15

Attachments:

• AdTsai-ghop-mcs.zip

[GoogleCodeExporter]

Great job! From your statistics, that's a really good change. Here are some 
tips on
submitting this change:

1) If you used SVN to check out your code, use "svn di" to create a diff. 
Otherwise,
you can use the diff tool (diff -c file1 file2) to make a "patch".
2) Try to submit multiple small patches. Each change should be the smallest 
change
that you can make that is a single unit (eg, if the change in file A depends on 
the
one in file B, submit them together). 
3) Did you make sure to run the test suites (in mcs/test)? Also, it's often 
wise to
do a full compile of the class libraries, just to double check.

Original comment by ben.maurer on 24 Dec 2007 at 3:20

[GoogleCodeExporter]

Some specific comments:

- Changed some Hashtables to use ListDictionaries instead. It was observed that 
some
HashTables only contained a few items in the vast majority of cases. Since
ListDictionary is more efficient on small sets (<10 elements), 
"known_variables" from
class ExplicitBlock as well as "labels" and "constants" from class Block were 
changed
to ListDictionaries.

Does this have the risk of making some code take quadratic time to compile 
(e.g., a
Block with 10000 labels)?

A good thing to do here would be to make a "worst possible case" test case and 
show
what (if any) performance degradation happens. If possible, try to design the 
patch
to act reasonably in the abnormal case and optimally in the normal case (eg, use
ListDictionary only if you have fewer than 10 items).

I'd try to get the smaller changes (eg, using an initially small arraylist, 
don't use
iterators) submitted first. These will be very easy to review. 

Original comment by ben.maurer on 24 Dec 2007 at 5:34

[GoogleCodeExporter]

I think a ListDictionary has a time complexity of O(n), while Hashtable should 
be 
near constant O(1). I did a test, and in the pathological case (100,000 
labels), the 
ListDictionary version is, indeed, much slower.

Using ListDictionary: 304.9s
Using Hashtable: 0.73s

That's ~400 times slower, in a worst case scenario. I'll see what can be done 
to 
alleviate it.

Original comment by AdT...@gmail.com on 25 Dec 2007 at 12:12

[GoogleCodeExporter]

A little crawling through MSDN has revealed the HybridDictionary class - 
apparently 
it defaults to a ListDictionary and automatically switches to a Hashtable when 
it 
becomes more optimal.

I switched to the HybridDictionary, and the pathological test case of 100,000 
labels 
now completes in about the same time as regular old Hashtable. There should be 
some 
overhead when HybridDictionary switches from ListDictionary to Hashtable, but 
in 
practice this should occur very rarely (>10 labels per block seems unlikely).

Also, I'm unfamiliar with SVN, and I'm not sure how to make series of patches. 
Since 
there's more than 1 change to make, should I make a change and create a patch 
then 
revert, make another change and create another patch then revert again, etc.? 
Or do 
I make a change, make a patch, make another change, make another patch, etc.?

Original comment by AdT...@gmail.com on 25 Dec 2007 at 1:35

[GoogleCodeExporter]

Good call on the HybridDictionary. There may be other places that call for this
technique. Are there any instances where you can use a "null" as an empty 
dictionary?
I noticed that the code does that already in some locations.

>Also, I'm unfamiliar with SVN, and I'm not sure how to make series of patches.
It depends. If you have changes to different files, just do:

svn di file1 > patch1.patch
svn di file2 > patch2.patch

Making changes to the same file is a bit trickier. For now, I'd use the 
diff/revert
method.

Merry Christmas!

Original comment by ben.maurer on 25 Dec 2007 at 3:28

[GoogleCodeExporter]

Btw, it might be worth having test cases for O(n^2) vs O(n) time in mcs/test. In
general, when you find a bug that mcs/test doesn't catch, you should try to put 
new
tests in there.

Original comment by ben.maurer on 25 Dec 2007 at 3:46

[GoogleCodeExporter]

Here are the updates, as well as the patches. The updated change log includes 
the 
name of the patch beside each change.

Original comment by AdT...@gmail.com on 26 Dec 2007 at 10:11

Attachments:

• [AdTsai-ghop-mcs v2.zip](https://storage.googleapis.com/google-code-attachments/google-highly-open-participation-mono/issue-4/comment-22/AdTsai-ghop-mcs v2.zip)

[GoogleCodeExporter]

Lovely detective work folks!

I am going to review this afternoon, this looks fantastic.

Btw, does anyone know if we can keep "reopening" this issue, as am sure we can 
find
more low-hanging fruit like this everywhere

Original comment by miguel.d...@gmail.com on 26 Dec 2007 at 3:36

[GoogleCodeExporter]

This is fantastic, memory usage on bootstrapping mcs went from:

Total memory allocated: 61717 KB

To:

Total memory allocated: 57490 KB

Is the code licensed under the MIT X11 license?

Original comment by miguel.d...@gmail.com on 27 Dec 2007 at 9:15

• Changed state: Closed

[GoogleCodeExporter]

For the record, one thing that is useful is to use HeapShot to profile 
applications,
more docs can be found here:

http://www.mono-project.com/HeapShot

You might want to add a ReadLine() before the compiler finishes to give you a 
chance
to snapshot memory usage.

Original comment by miguel.d...@gmail.com on 27 Dec 2007 at 9:33