|
|
|
|
|
|
|
Kathyrn went to the ACM SIGPLAN PLDI (Programming Language Design and Implementation) conference in Berlin at the end of last week so I was mentorless for the week. Before she left, Kathryn gave me some additional reading material and asked me to download Jikes RVM and GCTK, and ensure that they were working properly on my computer. I spent the week reading the garbage collection book and two other papers. I attempted to download Jikes RVM and GCTK but unfortunately Linux on the UT computers did not meet one of the prerequisites necessary to download Jikes RVM. I spent most of Tuesday afternoon with one of Kathryn's grad students, attempting to fix the problem, but we were unable to do so.
After a frustrating day at work, I cooled off at Barton Springs with the cs gang. We went earlier this time and the water definitely felt warmer to me! We went out to lunch almost everyday this week (for the first time EVER, I had Thai food and Indian food). On Wednesday Maria took Laurent, Kartik, and me to get rollerblades. I've wanted rollerblades since my first year in college so this purchase was definitely exciting.
It was Benoit's birthday on Thursday so we went out for lunch and had pie at
ACES (the building we work in) afterwards (candles and all
On Friday we went to the Veloway again and I got to test out my rollerblades for the first time! This proved to be slightly disastrous - as I proved to be slightly accident-prone. |
The new reading for this week included:
|
|
|
|
 In the morning, we went to Hamilton Pool, a warm swimming "hole" outside of Austin. The morning was spent swimming in the water, climbing the surrounding rocks, and...looking for a lost key.
Note to all swimmers out there: do not swim with your key in your pocket because
it is just bound to fall out! After a quick lunch we headed over to Lake Travis for some cliff-jumping. I am utterly afraid of heights and jumping 20-some feet into water was not exactly what I considered fun. But once I finally got the courage to jump, it wasn't so bad. The weather was beautiful and we spent the afternoon swimming, cliff-jumping, and playing Tarot on the rocks. After everyone had finally been eaten by too many fire ants, we headed to The Oasis to watch the sun set and to try out their margaritas. |
On Monday, Maria and I met with Kathryn and she told us that we would be working together on the garbage collection project. We met later that day in Kathryn's office to conference call with Steve Blackburn. Steve and Kathryn created the GCTk toolkit and Steve was going to be our resource on the Jikes RVM and the GCTk code. He helped us figure out why I was unable to download the Jikes RVM the previous week - the most important reason being that I needed to use a BASH shell. Steve also clarified some questions Maria and I had. He explained that we would be using our Intel boxes to compile both the Jikes RVM and the GCTk code, and then would be running the executable on a Power PC (in our case a Macintosh G4).
 After work, Benoit, Nicolas, Laurent, and I headed over to Serita's place to watch 10 Things I Hate About You. What a great movie! On Tuesday, Kathryn and Calvin had a meeting to tell us about PLDI and the papers presented. It was interesting to hear about the papers. Later that night, we again went over to Serita's but this time to play sand volleyball. In my opinion, the only way to play volleyball is in the sand! By the end of the week, Maria and I had successfully downloaded the Jikes RVM and GCTk to a shared disk space. Kathryn gave us two G4s to set up so we would have something to run our executables on, but we were unable to get them running because we needed network drops to be set up first. In the meantime, Maria and I decided to look at some of the GCTk code. Steve emailed us the names of a few functions to "browse." These included the implementation of a semi-space collector and a generational collector. Maria and I also spoke with Steve a few more times throughout the week. He explained the particular optimizations he wanted done to the code. The first task he gave us was to optimize TIB (type information block) allocation in GCTk's Appel generational copying collectors. |
In Appel generational copying garbage collection...
When a TIB is created, it is allocated to the nursery (just like other objects). However, TIBs do not die until the program terminates. Thus, as the garbage collector moves through the generations, the TIBs are copied over and over. This copying creates a considerable amount of unnecessary overhead.
The write barrier problem...
When an object is created, it is given a header. Every object has a header (array objects have a three-word header and non-array objects have a two-word header). One of the words in every header contains a pointer to the TIB. If an object is not in the same generation as the TIB, this pointer will be checked by the respective write barrier. Though the pointers do not need to be remembered (i.e. TIBs are always older than the object and young-old and intra-generational pointers do not need to be remembered), the write barrier must still check them, creating another source of unnecessary overhead.
The solution...
To get rid of both sources of overhead, we need to allocate
every TIB, at creation, to an "immortal space,"
where it can live for the rest of the program's life. This solution
will eliminate copying TIBs from generation to
generation. And because we now know that all TIBs live in the
immortal space, we do not need a write barrier for the space.
Omission of the write barrier allows us to eliminate the testing of
pointers whose target is a TIB.
New garbage collection reading for this week included:
|
|
|
|
Maria and I spent Monday and Tuesday setting up the G4s with Yellow Dog Linux (version 2.3) and discussing exactly how we were going to implement the TIB optimization. Installing Yellow Dog proved to be another source of frustration for Maria and me. Even with email help from Steve, we were unable to get Yellow Dog working by the time we left on Wednesday.
On Monday, Emery, one of Kathryn's graduate students, gave his thesis defense. His interest is in memory management, and through his dissertation work, he created Hoard, a scalable memory manager for multi-processors, as well as heap layers, which allows memory allocators to be made out of C++ layers. Later that evening, Laurent and I attempted to find a movie theatre. Not having much success, we stopped at The Outback Steakhouse (a great restaurant) and played pool on 6th Street.
Most of Wednesday was spent helping Maria pack food and camping equipment. When Ted was finished at work, we headed down to Padre. It took about four hours to get there (stops included). By the time we got to the island and traveled down the beach to find a good camping spot, it was dark. Putting up the tents was very difficult because of the dark and because it was very windy. I woke up the next morning covered in sand!
 We spent Thursday swimming, reading, and brushing the sand out of our tents. In the evening, Ted made a bonfire. We cooked dinner on it (and smores!) and sat talking late into the night. Friday morning we woke up at 5:45am to go back up the beach to see the park rangers release baby sea turtles into the ocean. Currently there are five endangered species of sea turtles. Because some of these turtles nest on Padre Island, National Park service workers scavenge the island from late-March through July in search of nests. When they find a nest, the workers incubate the eggs until they hatch. Once the turtles hatch, the workers release the baby turtles onto the beach and watch over them as they make their way to the water. Anyone interested in watching the turtle release is invited to come out and join the park rangers. Some sea turtle trivia:
|
|
|
|
|
My week at work was spent being frustrated at the Yellow Dog installation. For some reason we were having very bad luck with the installation process. With more help from Steve, Maria and I finally got it working mid-week and installed the Jikes RVM and GCTk on both of the G4s. The next thing we decided to do was to make sure that Jikes RVM and GCTk were working. We wrote a simple file that output "Hello World" and compiled and ran it. When we ran the file, we got an exception. When we told Steve about the exception, he compiled our program on his computer in Australia and ran it on our G4s - it worked for him. We didn't realize until the following week that the problem lay within the Intel box (Jikes on the UT system was outdated and, we believe, therefore not compatible with the version of Jikes RVM we were using).
Maria and I again looked at the GCTk code and decided that we would begin coding on the following Monday.
On Tuesday, we all went over to Maria's house to roller blade and play
Kill Dr. Lucky. I saw two
good movies this week - A.I. and The Others. On Friday, I went with Benoit, Nicolas,
and Laurent to one of their friend's party and had my first experience with French food (crepes are
good!).
|
|
|
|
On Sunday, Maria cooked Ted, JP, and me a traditional Swedish dinner.
At work, Maria and I spent most of the week coding the TIB optimization. After we attempted to compile and run our code and got another exception error, we realized that the problem was with the compilation (see above for the possible explanation). Since Australia is 14 hours ahead of Texas, Steve set up an account on his computer so we could compile code (since he is not using his computer when we are working). In an attempt to solve our problem, Maria installed the version of Jikes that Steve had on his computer to the UT server, but we still could not get HelloWorld or GCTk to run without an exception. How frustrating!
On Friday, I compiled the code on Steve's computer and ran our optimization...there was output! I didn't know whether the output was correct but it was a very exciting moment to see numbers on the screen!
Fun stuff for the week included having a Flaming Dr Pepper and seeing Bob Schneider (a local music artist) sing at Antone's on 6th street (Bob Schneider sang for 3 hours...the concert never seemed to end!).
|
|
|
|
Maria and I had been looking forward to this week for some time - Steve was here! He and Kathryn were going to a DeCapo meeting in Colorado on July 29 and Kathryn had convinced him to come a week earlier to work on GCTk stuff.
Kathryn and Steve spent much of Monday and Tuesday in meetings so I worked on my webpage and Maria worked on her graphics research.
Tuesday night Kathryn had a potluck dinner in honor of her students that had recently gotten their phds and for those that were soon going to defend.
Wednesday morning, Maria and I came in early to meet with Steve (much
to Maria's dismay - she wanted to stay home and watch the Tour de
France 
). Steve
explained how to analyze the output from GCTk, as there was no
documentation on what the statistics meant. We showed him the
output we were getting with our TIB optimization and soon realized
that no objects were being allocated into the immortal space we had
implemented (the statistics should have shown
allocation into the immortal space). We
spent a few hours debugging the code without much success (there was
definitely some weird compiler behavior happening). However, by the
end of the day, we had corrected two errors in the code and the TIBs
were now being allocated into the immortal space.
Thursday and Friday went by incredibly fast. Maria and I spent the mornings and afternoons talking with Kathryn and Steve about how to test our TIB optimization, Beltway, and what the next step of the project was.
To test our TIB optimization on the Appel collector, Steve advised us to use:
The next step in the project was to implement the TIB optimization in the Beltway collector. Steve explained some of the key methods in the code (what they did, how they would need changed, etc.) and we discussed generally how the changes in Beltway should affect the collector's performance.
Thursday night, the cs gang headed out to the Veloway again. It had
been awhile since we'd been there and it was great to go skating
again. On Friday, we went to Barton Springs - this time, however, I
was not brave enough to get into the water - it was too cold!
|
|
|
|
After Steve and Kathryn left, I created the appropriate Appel configuration files for the above cases and Maria wrote a script to compile all of them (there were a total of 12 compilations we needed to do and with the script, we could leave them to build overnight).
The next day Maria found that all of the files had compiled successfully, but when she went to run Steve's scripts, she received an error message. She tried all week to get the scripts to run but was not successful.
For the rest of the week, I worked on changing the Beltway code to accomodate the TIB optimization. I ran into a lot of questions and emailed Steve and Kathryn with them. Kathryn came back to Austin on Thursday and answered the questions. By the end of Friday, however, I had come up with some more questions about the code.
Tuesday morning, I received an odd email from my father stating that the airline I was supposed to fly home on had gone out of business. I went to the airline's website and could not find anything to confirm my Dad's email. After googling for Vanguard Airlines, I found an article on CNN stating that indeed the airline had gone out of business the day before. Luckily (well...actually unfortunately for me because I don't want to leave Austin), the travel agent who arranged my original flight was able to book me on another airline for the same date as my original return flight.
Also, on Tuesday, Maria bought Unexploded Cow, another
wonderful game from the makers of Kill Dr. Lucky. We played it
on Thursday and Friday, destressing by blowing up cows. After playing
Unexploded Cow on Friday, JP, Laurent, Benoit, and I went to
the Dobi Mall. There is a game store in the mall that stays open late
on Friday nights to give customers a chance to come in and play any
game in the store. We
tried out a few games and finally ended up playing a game called
Apples to Apples. It was very enjoyable!
|
|
|
|
 On Saturday morning, we all headed up to Maria's house to spend the day playing games and roller blading. Unfortunately when it was finally cool enough outside to roller blade, it began to rain. Maria and I spent Monday and Tuesday finishing up our modifications to the Beltway code. Steve sent us a detailed email with the answers to all of our questions from the previous week, which was really helpful. We conference called with him Monday afternoon and he was able to clear up further issues we were having. On Monday, Kathryn told me that I would be giving a presentation the following Tuesday on the research I had done this summer. I was slightly nervous about this because I do not like speaking in front of people. Tuesday night, JP had all of us over to his apartment to play Tetrinet (Tetris where up to 6 people can play against one another). JP's place was crowded. On Wednesday, Maria got the scripts to run for Appel and we had stats indicating the change in performance from our TIB optimization. One of the scripts that Steve had given us, graphed the results (i.e.
|
The results for javac are similar to the ones we got for the rest of the benchmarks. The interesting thing that should be noted from the graphs is that the lines representing TIB in immortal space, write barrier off and TIB not in immortal space, write barrier off are much less than TIB in immortal space, write barrier on and TIB not in immortal space, write barrier on (i.e. Appel with no changes). In some of the other benchmarks this difference was as much as 10%. This indicates that removing the TIB write barrier decreases run-time. Putting the TIBs in an immortal space does not give us much of an advantage.
We can use these results to hypothesize how our TIB optimization will affect Beltway. We believe that again the TIB write barrier will reduce the runtime and that putting the TIBs in an immortal belt will not have much (if any) effect. Optimistically, we are hoping that removing the TIB write barrier will make even more of a difference in Beltway than it did in Appel.
We talked to Steve on Wednesday about the results and he was very excited (as were we!). I spent Thursday and Friday working on my presentation. Having to do a presentation on my research turned out to be a really good thing. I got a chance to review what we did, why we did it, and the process we took, which gave me a better understanding of the project.
On Thursday we went out to Slick Willie's to play pool. And on Friday Maria was nice enough to let me stay at her house to work on my presentation all evening. Being at her house gave me an opportunity to ask Maria questions if I ran into problems explaining our research.
|
|
|
|
 After a long night of garbage collection, I was pleased to wake up and go out to Lake Travis with the cs gang on Saturday. We went to the same place we had gone cliff jumping on my birthday and I was amazed to see that what was once a 20-some feet high cliff was now reduced to 3 feet above water. (the water in Lake Travis was so high because of rainstorms in July). We played in the water for awhile and then moved down the lake to higher cliffs. At this point, it started to thunder and lightning so we headed back to Maria's house to play games. On Sunday I came up to ACES to work on my presentation and was lucky enough to get an email from Steve. He looked at my power point slides and gave me a call so we could chat abou them. He gave me some good suggestions to improve them. It was very helpful!
|
|
|
|
|
