Blog

Why Google Stores Billions of Lines of Code in a Single Repository

062016_CACMpg79_Why-Google.largeEarly Google employees decided to work with a shared codebase managed through a centralized source control system. This approach has served Google well for more than 16 years, and today the vast majority of Google’s software assets continues to be stored in a single, shared repository. Meanwhile, the number of Google software developers has steadily increased, and the size of the Google codebase has grown exponentially (see Figure 1). As a result, the technology used to host the codebase has also evolved significantly.

Back to TopKey InsightsThis article outlines the scale of that codebase and details Google’s custom-built monolithic source repository and the reasons the model was chosen. Google uses a homegrown version-control system to host one large codebase visible to, and used by, most of the software developers in the company. This centralized system is the foundation of many of Google’s developer workflows. Here, we provide background on the systems and workflows that make feasible managing and working productively with such a large repository. We explain Google’s “trunk-based development” strategy and the support systems that structure workflow and keep Google’s codebase healthy, including software for static analysis, code cleanup, and streamlined code review.

Source: Why Google Stores Billions of Lines of Code in a Single Repository | July 2016 | Communications of the ACM

Booming Enrollments in Computer Science

At the Computing Research Association (CRA) Snowbird conference in 2014, Jim Kurose (then at University of Massachusetts-Amherst) and Ed Lazowska (University of Washington) presented a session on burgeoning enrollments in U.S. computing courses. In response, CRA’s Board formed a committee to further study enrollment-related issues, chaired by CRA board member Tracy Camp.

A panel on the upsurge in undergraduate computer science (CS) enrollments in the U.S. took place at the ACM Special Interest Group on Computer Science Education Technical Symposium last year (SIGCSE 2015); shortly thereafter, the full committee went to work with the goal of measuring, assessing, and better understanding enrollment trends and their impact, with a special focus on diversity.

Explained Susan B. Davidson, CRA Board Chair and a member of the CRA enrollments committee, “Over the past few years, computing departments across the country have faced huge increases in course enrollments. To understand the extent and nature of these ‘booming enrollments,’ CRA has undertaken a study that surveys both CRA-member doctoral departments as well as ACM non-doctoral departments.”

In addition to attempting to identify the extent of the “boom” in CS enrollments, Davison said, “We are trying to understand which students are making up this boom: CS majors? Students from other fields seeking to minor in CS? Students in other fields taking a course or two in CS? And why are they doing so; what is driving them?”

Source: Booming Enrollments | July 2016 | Communications of the ACM

SyntaxHighlighter plugin for displaying code in WordPress

This is a well-known plugin, so I am not divulging a secret, but I really like how it enables elegant code display in WordPress. See https://wordpress.org/plugins/syntaxhighlighter/ and https://en.support.wordpress.com/code/posting-source-code/ for the details. I attach the display of a C program that computes bits, in a very efficient way, from the Ehrenfeucht-Mycielski sequence. See the On the Ehrenfeucht-Mycielski sequence paper in the publications list.

[code language=”c”]
// Calculates bits of Ehrenfeucht-Mycielski sequence
// by Grzegorz Herman and Michael Soltys
// December 2007
//
// Usage:
// generate <n>
// with <n> being the requested number of bits.
// Warning: uses 57 Bytes of RAM per generated bit

#include "malloc.h"

// structures used
struct branch
{
char* l;
char* r;
struct node* n;
};
struct node
{
char* p;
struct branch b[2];
};

// data pointers
char* dhead;
char* dtail;
// node pointers
struct node* nhead;
struct node* ntail;

// creates a new node
struct node* newnode(char* p)
{
struct node* n;
n = ++ntail;
n->p = p;
return n;
}

// updates branch information
void setbranch(struct node* u, char b, char* l, char* r, struct node* n)
{
u->b[b].l = l;
u->b[b].r = r;
u->b[b].n = n;
}

// calculates the matching bit
char nextb(char bit)
{
char *f, *i, *j, *k, *l;
char ci, cj, ck;
struct node *u, *v, *w;
*(++dtail) = bit;
f = i = dtail;
u = nhead;
while (1)
{
f = u->p + 1;
u->p = dtail;
k = i;
ck = *k & 1;
w = u->b[ck].n;
if (w == NULL)
break;
l = u->b[ck].l;
j = u->b[ck].r;
while (j > l)
{
ci = *i & 1;
cj = *j & 1;
if (ci != cj)
{
// split existing branch
f = w->p + 1;
v = newnode(dtail);
setbranch(v, cj, l, j, w);
setbranch(v, ci, dhead, i, newnode(dtail));
setbranch(u, ck, i, k, v);
return *f;
}
i–, j–;
}
// follow existing branch
v = u->b[ck].n;
setbranch(u, ck, i, k, v);
u = v;
}
// add new branch
ci = *i & 1;
setbranch(u, ci, dhead, i, newnode(dtail));
return *f;
}

int main(int argc, char* argv[])
{
int n;
char* c;
n = 0;
for (c = argv[1]; *c; ++c)
n = 10*n + *c – ‘0’;
// initialize
dhead = dtail = (char*) malloc((n+2)*sizeof(char));
nhead = ntail = (struct node*) malloc(2*n*sizeof(struct node));
nhead->p = dhead;
// build
char b = ‘0’;
while (dtail < dhead+n)
b = (‘0’+’1’) – nextb(b);
// output
*(++dtail) = ‘\n’;
write(1, dhead+1, dtail-dhead);
return 0;
}
[/code]

Mechatronics Engineering Launch at CI

28458926065_ae45658ca8_z 28458926955_c09f6c0347_zYesterday we participated in the launch of Mechatronics Engineering at CI. This new program will be housed under Computer Science, and the first group of students is going to be admitted in the Fall 2018.

We were honored to have Assembly Member Jacqui Irwin who helped secure the funds to start engineering at CI, and the event was presided by President Rush, in one of his last appearances before his retirement.

The event was held in the lobby of Sierra Hall, the new STEM building, with Computer Science labs on the first floor, and demos of faculty/student projects in the Robotics lab and the Embedded systems lab.

Postdoctoral position in Algorithms at Bristol Univ.

POSTDOCTORAL POSITION IN ALGORITHMS RESEARCH AND/OR LOWER BOUNDS

Application deadline 1 August, 2016. Start date negotiable but
ideally by Autumn/Fall 2016.

Salary: 35,609 to £40,082 UK pounds

This is a fixed term appointment terminating end of December 2017.

The Algorithms team in the Department of Computer Science at Bristol
University is looking to hire a postdoctoral researcher in the areas
of algorithms research and/or lower bounds. The post will require a
high level of expertise in areas which may include but not be limited
to data structures/algorithms, discrete probability, discrete
mathematics and combinatorics.

Our current work focuses on algorithms and lower bounds for streaming
and dynamically changing
data however we also have a broader interest in other aspects of
algorithms/theory research.

The ideal candidate will have a Ph.D. in theoretical computer science
(“Track A”) or closely related mathematical area together with a
strong track record of international publications in algorithms or
theoretical computer science (“Track A”) venues. This may include for
example, ICALP/SODA/STOC/FOCS.
Please see http://bit.ly/29jXodA for full details both of the post and
the application process.

Jason Isaacs: More independence for drone operation makes for promising future in business, educatio

The first half of 2016 has been an exciting one for those of us working in the sUAS (small Unmanned Aircraft Systems) industry. Commonly known as drones, these devices are currently being used in such areas as search and rescue, firefighting, wildlife monitoring, aerial photography, precision agriculture and many other arenas. In fact, Intel is experimenting with choreographed light displays involving hundreds of sUAS that may one day provide a safer alternative to fireworks shows, especially in fire prone areas like Southern California.

Source: Jason Isaacs: More independence for drone operation makes for promising future in business, educatio

Hike to the Tri-Peaks on Boney Mountain

IMG_9165 IMG_1226 IMG_1218On June 12 we hiked to the top of the Boney Mountain, and we reached the Tri-Peak formation, which is one of several peaks on top of Boney. There is a nice description of this somewhat challenging hike here.

My companion was Adam Sędziwy, who also gave a talk in Computer Science at CI; it was very appropriate that from the top of the Tri-Peaks we were able to see both the CI campus, and the Channel Islands.