Posts from January 2013

C++ containers that save memory and time

Thursday, January 31, 2013

We’re pleased to announce C++ B-Tree, a C++ template library that implements B-tree containers with an analogous interface to the standard STL map, set, multimap, and multiset containers. B-trees are well-known data structures for organizing secondary storage, because they are optimized for reading and writing large blocks of data. But the same property that makes B-trees appropriate for use with databases and file systems also makes them appropriate for use in main-memory, just with smaller blocks.

C++ standard libraries commonly implement the map and set data structures using Red-Black trees, which store one element per node, requiring three pointers plus one bit of information per element to keep the tree balanced. By comparison, B-tree containers store a number of elements per node, thereby reducing pointer overhead and saving a significant amount of memory. For small data types, B-tree containers typically reduce memory use by 50 to 80% compared with Red-Black tree containers.

insertion time as a function of tree size
(256 byte node)

Storing multiple elements per node can also improve performance, especially in large containers with inexpensive key-compare functions (e.g., integer keys using less-than), relative to Red-Black tree containers. This is because performance in these cases is effectively governed by the number of cache misses, not the number of key-compare operations. For large data sets, using these B-tree containers will save memory and improve performance.

insertion time as a function of node size
(10M element tree)

These templates are nearly drop-in compatible with the STL map, set, multimap, and multiset types, with one significant exception. Unlike the standard container types, insertions and deletions invalidate outstanding iterators (we provide “safe” alternatives to handle this case).

By Josh MacDonald, 20% Contributor

Google Code-in 2012: it’s numbers time

Tuesday, January 29, 2013

Earlier this month, Google Code-in, a contest introducing 13-17 year olds to open source software development, finished up with really exciting results.

We had 334 students from 36 countries complete 1,925 tasks in the 7 week contest.  Students worked with 10 open source organizations on coding, documentation, training, user interface, research, outreach tasks, and quality assurance tasks. 58.7% of students completed at least 3 tasks in the contest.

The countries with the most students completing tasks are shown in the pie chart below:
This year there were 5 countries who for the first time had students complete tasks in Google Code-in: China, Kenya, Kuwait, Trinidad and Tobago, and Uruguay.

Pre-university/high schools
The 5 schools with the most students completing tasks in Google Code-in 2012 are listed below.
- Technical School Electronic Systems (associated with Technical University- Sofia) in Bulgaria had the most students participating in the contest for the second year in a row with 44!
- Dunman High School in Singapore had 13 students participate in this year’s contest (only 1 student from all of Singapore participated last year).
There was a 3 way tie between the following schools to wrap up the 5 participating schools:
- Marc Garneau Collegiate Institute in Canada
- Precious Blood Secondary School in Kenya (an all girls school)
- Colegiul National “Mircea cel Batran” in Romania

Age of Students

There were 174 dedicated mentors from 40 countries guiding students throughout the contest. This year we had mentors from a few new countries including Macedonia, Panama, Paraguay, Uruguay, and the Slovak Republic.

A huge thank you to all of the students, mentors and organization administrators who made Google Code-in 2012 a success! And thank you to all the parents and teachers who encouraged students to learn more about open source software development!

Stay tuned to this blog for the announcement of the 20 Grand Prize winners on February 4th.

By Stephanie Taylor, Open Source Programs Office

XBMC Rocked the Summer

Thursday, January 24, 2013

XBMC is an open source software media player and entertainment hub available on Windows, OSX, Linux, and iOS, and available in beta form on Android and the Raspberry Pi.

2012 was XBMC's second year participating in Google Summer of Code, having previously been involved back in 2008, and it was enormously successful with all four accepted students completing their projects and adding valuable code to the XBMC base.

Sascha Montellese set out to provide a simpler and more powerful method for filtering the contents of a user's XBMC Media library. While theoretically a simple task, Sascha found himself upgrading virtually every piece of the XBMC library/database, providing vast improvements for the entire user experience, all to ensure that his advanced filter could reliably filter by nearly all popular media categories, including rating, progress, release date, genre, etc.

While Sascha sought to make the data in XBMC's library more easily accessible for users, Tobias Arrskog's goal was to more efficiently and effectively gather that data from the internet using a data-driven approach. After extensive statistical research, Tobias created a data scraper called Heimdall, designed to be both more efficient and "future proof," allowing for the addition of future media types, such as games.

Tobias sought to improve the data inside the XBMC library and Sascha sought to improve the XBMC library itself. Alasdair Campbell, in turn, sought a way to better share the media of the XBMC library with a user's entire media viewing ecosystem. To that end, Alasdair's project was to improve UPnP support on the XBMC UPnP server. By the end of the summer, Alasdair had realized a great deal of his goal, marking the first steps to a truly practical XBMC Server.

Finally, Andres Mejia's project differed somewhat from the other three projects. While the other projects were designed to enhance the XBMC library in various ways, Andres was tasked with creating an XBMC Test Suite so that XBMC developers could more easily test for various bugs before, during, and after the build process. Andres's Test Suite was merged into the XBMC codebase at the end of the summer.

When XBMC applied for Google Summer of Code in 2012, our entry was thought of primarily as a nice community event that could get more developers excited about the project. It has been incredible to discover the extent to which this program has vastly improved the codebase in ways that are reaching our users almost immediately. We will be very excited to apply for future instances of Google Summer of Code.

By Nathan Betzen, XBMC Google Summer of Code Administrator

Find sample code and more for Google Cloud Platform, now on GitHub

Tuesday, January 22, 2013

Today, we’re announcing that you can now find Google Cloud Platform on GitHub! The GitHub organization for the Google Cloud Platform is your destination for samples and tools relating to App Engine, BigQuery, Compute Engine, Cloud SQL, and Cloud Storage. Most Google Cloud Platform existing open source tools will be migrated to the organization over time. You can quickly get your app running by forking any of our repositories and diving into the code.

Currently, the GitHub organization for the Google Cloud Platform has 36 public repositories, some of which are currently undergoing their initial code reviews, which you can follow on the repo. The Google Cloud Platform Developer Relations Team will be using GitHub to maintain our starter projects, which show how to get started with our APIs using different stacks. We will continue to add repositories that illustrate solutions, such as the classic guest book app on Google App Engine. For good measure, you will also see some tools that will make your life easier, such as an OAuth 2.0 helper.

From getting started with Python on Google Cloud Storage to monitoring your Google Compute Engine instances with App Engine, our GitHub organization is home to it all.

Trick of the trade: to find samples relating to a specific platform, try filtering on the name in the “Find a Repository” text field.

We set up this organization not only to give you an easy way to find and follow our samples, but also to give you a way to get involved and start hacking alongside us. We’ll be monitoring our repositories for any reported issues as well as for pull requests. If you’re interested in seeing what a code review looks like for Google’s open source code, you can follow along with the discussion happening right on the commits.

Let us know about your suggestions for samples. We look forward to seeing what you create!

By Julia Ferraioli, Developer Advocate, Google Compute Engine

Google Code-in 2012 comes to a close

Monday, January 14, 2013

Congratulations to the 334* students who have been busy completing 1,913* tasks for the last seven weeks in the Google Code-in contest.  The 13-17 year-old students received a hands-on introduction to open source software development by working directly with 10 open source projects that have developed tasks for the students, complete with mentors to offer guidance along the way.

Students completed tasks like writing small pieces of code, creating tutorials to help new users of the software, reporting bugs, writing documentation for the open source projects and everything in between.

Stay tuned to this blog as we will be announcing the 20 Grand Prize Winners (2 from each open source organization) on February 4th. The Grand Prize Winners receive a trip for themselves and a parent/legal guardian to Google’s Mountain View, CA headquarters for four days this April where they will meet with Google engineers, explore the Google campus and enjoy a day full of adventures in San Francisco.

Congratulations again students on your accomplishments, we hope you had fun working with the open source organizations and mentors and will continue to stay involved in the community or with other open source projects in the future.

A huge thank you to all of the mentors and organization administrators who have spent many busy nights and weekends helping students learn about the many aspects of open source software development. This contest would not be possible without all of your dedication and excitement in sharing your passion for your projects with these students.

In the next few weeks we will post more stats on the contest and snippets about some of the extraordinary work the students completed during the Google Code-in.

Great job Students, Mentors and Organization Administrators!

* The final evaluations are currently being graded, these numbers will likely rise in the next few days.

By Stephanie Taylor, Open Source Programs

Google Document Sprint 2012 - 3 more Books Written in 3 days

Wednesday, January 9, 2013

Last month the Google Open Source Programs Office hosted its second Google Summer of Code Document Sprint where three open source projects successfully wrote an entire book documenting how to use their project’s software in less than a week.  The three open source projects that participated were the Evergreen Project, Etoys, and FontForge. The Evergreen Project is an integrated library system that helps library patrons find library materials, and helps libraries manage, catalog, and circulate those materials.  Etoys is a child-friendly program language for use in education. And FontForge is an outline font editor that allows users to create and edit their own fonts. Dedicated volunteers came from all around the globe to collaborate with one another to create a book their entire project would be able to reference and update for years to come.

Below is a guest post from Kathy Lussier, an Evergreen participant describing the process of this fast and furious way to collaboratively write a book on software documentation.
How long does it take to write a 116-page manual introducing Evergreen administrators to basic setup, configuration and maintenance? If you bring together a dedicated documentation team, great facilitators, and the right environment, it turns out you can do it with just three days (or closer to two and a half days) of focused writing.
Lindsay Stratton (from left), Robert Soulliere, Kathy Lussier and Dan Scott at the Googleplex for the Google Summer of Code Documentation Sprint. 
I had the opportunity to work last week with four of my Evergreen colleagues to create such a manual. Traveling to Mountain View, California, I joined Robert Soulliere of Mohawk College, Lindsay Stratton of Pioneer Library System and Dan Scott of Laurentian University for the Google Summer of Code Documentation Sprint. Our final team member, Jim Keenan of C/W MARS, could not make the trip, but joined us daily via Google+ Hangouts to make his contributions to the effort. 
On day 1, Allen Gunn (Gunner) of Aspiration facilitated an unconference where participants collaborated on topics like keeping documentation up to date with rapid development, user communities, documentation tools, and documentation-driven development. The unconference helped the participants become comfortable with one another enabling them to  speak freely about their ideas and opinions and began the team-building process that continued through the rest of the week. 
By the end of the first day, the team had created a title and tagline for our future book: Evergreen in Action: So you’ve installed Evergreen — now what? 
The target audience for the book is Evergreen administrators who have successfully installed Evergreen and now need to load data and configure the system. The goal was not to provide a comprehensive overview for each possible configuration option in the system, but to present the basic steps required to get up and running, focusing on common use cases. With the basic framework in our heads, we entered day two with what was to be the most difficult part of the process: creating a table of contents for the book. Adam Hyde of Floss Manuals provided guidance to the teams as they progressed through the process of shaping their books. 
We wrote our content ideas down on sticky notes and tried to arrange them in a logical order, a difficult task when so many pieces of the system are interconnected with each other. By lunchtime, when the table of contents was supposed to be finished, we still had far more chapters than could be completed by a team of five people in less than three days. The team then needed to go through the process of “killing our darlings,” dropping some desired chapters from the manual, but also leaving an opportunity for others in the community to contribute their knowledge and expertise at a later date.
Jim Keenan contributed remotely via a Google Hangout. 
Once the table of contents was completed, the next two and a half days fell into place as each of the team members wrote their chapters. They were long days, but the team worked well together, focusing on their areas of expertise while periodically asking questions of each other or even sometimes consulting the always-helpful IRC community. Our team’s strength was the diversity in skills among its members, leading to a fuller and richer manual, just as the diverse skills in the larger Evergreen community have led to a stronger ILS and vibrant support community. 
With the book done, Gunner facilitated another unconference on the final day where we talked about ways to sustain the work we started at the conference. 
I want to send along a final thanks to the Google Open Source Program Office for sponsoring the program, to Gunner for getting us energized, to Adam Hyde for guiding us through the book-creation process, and to all those in the community who answered our questions throughout the week. 
By Kathy Lussier, Evergreen Contributor

Google is excited to support the need for good, clear documentation of free and open source software with the three projects this year as well as the four projects from last year’s successful Document Sprint.

By Stephanie Taylor, Google Open Source Programs

Freeing up the summer with LibreOffice

Monday, January 7, 2013

LibreOffice is a comprehensive personal productivity suite for Windows, Macintosh, and GNU/Linux that helps you with your document production and data processing needs. LibreOffice had 10 students for Google Summer of Code 2012, 9 of whom successfully completed their projects. Some highlights of the students’ work is below.

  • Calc performance improvement from Daniel Bankston   Daniel improved the load time of both ODF and XLSX format in many ways. In large XLSX files, the improvement can be as big as loading in a mere 6 seconds compared to the previous load time of more than 8 minutes!
  • Enhanced Impress SVG export filter from Marco Cecchetti   Marco improved his previous work to export slides in SVG by adding animations features. Thanks to his work, you will only need to have Firefox around to play your presentations anywhere.
  • A MS Publisher import filter from Brennan Vincent   Brennan’s work was particularly hard because he had to reverse-engineer the file format. Together with Valek Filipov, they managed to cover the MS Publisher format from 97 to 2010 – with all the shapes, fills, and text properties that Open Document Graphics supports.
  • A Java GUI to pick up files for LibreOffice on Android from Iain Billett  Iain’s work is particularly important for the LibreOffice Android port. He implemented a UI that allows you to pick the documents to display, move to other pages and gives you the ability to zoom in on a document.
  • A new templates selection UI from Rafael Dominguez   Rafael worked on creating a modern UI to pick a template when creating a new document. He also added support to connect to remote repositories of templates which will soon help us to connect directly to the LibreOffice templates site.
  • Signed PDF export from Gökçen Eraslan   Thanks to Gökçen, we can now digitally sign the PDFs directly as they are produced by LibreOffice. This is very important for the security and trust in electronic documents to be maintained.
  • Android impress remote control from Andrzej Hunt   Andrzej’s Android Remote Control allows you to control the slideshow directly from your Android mobile phone.  Just connect your phone to the presenting computer via network or bluetooth, and you will see previews of the slides on the phone, and will be able to navigate that – instead of using the computer’s keyboard or usb remote control.

  • Improved group session and UI for collaborative editing of files from Matúš Kukan   Matúš advanced the Calc collaboration demo by adding user interface and continuing on the core work.  This work, once completed, will allow you to collaboratively edit one spreadsheet with your colleague conveniently, as if you chatted with them on an instant messenger, without the need to send multiple files around.
  • Unit tests improvements from Artur Dorda   Unit tests are extremely important for LibreOffice.  They are the tests that are run during the build time, and consequently are run by every developer that builds LibreOffice.  Unit tests help you to make sure that the functionality hasn’t regressed over time, and if it has, to help you discover the regression quickly.  Artur extended the unit tests mainly in the area of Calc.

The students’ code is already in the LibreOffice master branch either as an experimental feature or it is already in use.

Thanks to Google and their friendly Open Source Program team for organizing Google Summer of Code again this year and allowing us to participate.

By Cedric Bosdonnat, LibreOffice Organization Administrator

Google Summer of Code Mentor Mania

Thursday, January 3, 2013

This is a guest post from one of this year’s Google Summer of Code Mentors (also a former student in the program).

Google Summer of Code 2012 Mentor Summit
2012 Google Summer of Code Mentor Summit Group Photo- ~275 attendees
Picture taken by Robin Smidsrød, CC-BY-SA license

Once a year, open source enthusiasts the world over converge on Silicon Valley for a unique meeting called the Google Summer of Code Mentor Summit, a gathering of mentors from the organizations that take part in the Google Summer of Code program. Attendees come in all sizes, shapes and fields – they are men, women, young, old, experts, newcomers, academics, students, engineers, managers and open source evangelists. Though diverse and unique in their own way, each of the attendees and their organizations has one thing in common – the desire to build and maintain high quality open source software second to none.

As a first time attendee, my goals coming into the summit were simple: to make connections with other open source organizations, to compare their hierarchy, management and community against that of my own organization, to gain practical hands on experience and last but not least, to try and comprehend Google’s relationship with the open source organizations they spend millions of dollars on each year.

Looking back at my experience during the summit, I marvel at the capability, resourcefulness and above all openness of the summit attendees. In the eyes of these participants, all were equal. No organization was ‘small’ or ‘crude’. No one was ‘losing’, only winning. Everything that occurred at the summit was as far away from the traditional corporate culture which I had come to loathe as it could possibly be. It was also interesting to see that my fellow attendees were far more efficient and results driven than any corporate type I had ever met. Attendees made friends easily, discussed ideas freely, and most importantly, accepted and offered criticism freely. No one was rude or overbearing – it was merely our nature to sit down and discuss what’s being done and what could be done even better in the Google Summer of Code program.

Flying into the meeting, I asked OpenMRS community manager Michael Downey which important people would be attending the summit. The answer I expected was (of course) Chris DiBona, Director of the Google Open Source Programs Office, delegates from KDE and the Apache Software Foundation, and perhaps a guest appearance by a Google executive. However, Michael’s answer was ‘Us. We’re all important’. Unfortunately, I could not comprehend the true meaning of this statement until my first few hours at the mentor summit. Indeed, at the Google Summer of Code Mentor Summit, we were all certainly important.

As opposed to ‘ordinary’ summits organized by corporate sponsors, the Google Open Source Programs team had taken every effort to ensure that the attendees themselves decided the proceedings of the sessions. Mentors were encouraged to speak out, contradict, and criticize (which many often did). They were listened to with open minds, and given the opportunity to defend their arguments. The Google Open Source Programs team listened to all proposals and offered realistic feedback. The more boisterous proposals received “no’s”, as opposed to patronizing “maybe’s”, while the more plausible ones received approval to go into the next phase of discussions. In fact, this year’s conference had been amended based on the feedback provided during last year’s summit.

My impressions of the interaction between the sponsors and the attendees were that both parties clearly understood the roles and responsibilities of their relationship, and addressed them in a responsible and mature way. Clearly, both Google Summer of Code mentors and the Google Open Source team were all awesome people.

By Suranga Nath Kasthurirathne, OpenMRS 2012 Mentor and 2011 Google Summer of Code student