Game Performance: Data-Oriented Programming

Posted by Shanee Nishry, Game Developer Advocate

To improve game performance, we’d like to highlight a programming paradigm that will help you maximize your CPU potential, make your game more efficient, and code smarter.

Before we get into detail of data-oriented programming, let’s explain the problems it solves and common pitfalls for programmers.

Memory

The first thing a programmer must understand is that memory is slow and the way you code affects how efficiently it is utilized. Inefficient memory layout and order of operations forces the CPU idle waiting for memory so it can proceed doing work.

The easiest way to demonstrate is by using an example. Take this simple code for instance:

char data[1000000]; // One Million bytes
unsigned int sum = 0;

for ( int i = 0; i < 1000000; ++i )
{
  sum += data[ i ];
}

An array of one million bytes is declared and iterated on one byte at a time. Now let's change things a little to illustrate the underlying hardware. Changes marked in bold:

char data[16000000]; // Sixteen Million bytes
unsigned int sum = 0;

for ( int i = 0; i < 16000000; i += 16 )
{
  sum += data[ i ];
}

The array is changed to contain sixteen million bytes and we iterate over one million of them, skipping 16 at a time.

A quick look suggests there shouldn't be any effect on performance as the code is translated to the same number of instructions and runs the same number of times, however that is not the case. Here is the difference graph. Note that this is on a logarithmic scale--if the scale were linear, the performance difference would be too large to display on any reasonably-sized graph!


Graph in logarithmic scale

The simple change making the loop skip 16 bytes at a time makes the program run 5 times slower!

The average difference in performance is 5x and is consistent when iterating 1,000 bytes up to a million bytes, sometimes increasing up to 7x. This is a serious change in performance.

Note: The benchmark was run on multiple hardware configurations including a desktop with Intel 5930K 3.50GHz CPU, a Macbook Pro Retina laptop with 2.6 GHz Intel i7 CPU and Android Nexus 5 and Nexus 6 devices. The results were pretty consistent.

If you wish to replicate the test, you might have to ensure the memory is out of the cache before running the loop because some compilers will cache the array on declaration. Read below to understand more on how it works.

Explanation

What happens in the example is quite simply explained when you understand how the CPU accesses data. The CPU can’t access data in RAM; the data must be copied to the cache, a smaller but extremely fast memory line which resides near the CPU chip.

When the program starts, the CPU is set to run an instruction on part of the array but that data is still not in the cache, therefore causing a cache miss and forcing the CPU to wait for the data to be copied into the cache.

For simplicity sake, assume a cache size of 16 bytes for the L1 cache line, this means 16 bytes will be copied starting from the requested address for the instruction.

In the first code example, the program next tries to operate on the following byte, which is already copied into the cache following the initial cache miss, therefore continuing smoothly. This is also true for the next 14 bytes. After 16 bytes, since the first cache miss the loop, will encounter another cache miss and the CPU will again wait for data to operate on, copying the next 16 bytes into the cache.

In the second code sample, the loop skips 16 bytes at a time but hardware continues to operate the same. The cache copies the 16 subsequent bytes each time it encounters a cache miss which means the loop will trigger a cache miss with each iteration and cause the CPU to wait idle for data each time!

Note: Modern hardware implements cache prefetch algorithms to prevent incurring a cache miss per frame, but even with prefetching, more bandwidth is used and performance is lower in our example test.

In reality the cache lines tend to be larger than 16 bytes, the program would run much slower if it were to wait for data at every iteration. A Krait-400 found in the Nexus 5 has a L0 data cache of 4 KB with 64 Bytes per line.

If you are wondering why cache lines are so small, the main reason is that making fast memory is expensive.

Data-Oriented Design

The way to solve such performance issues is by designing your data to fit into the cache and have the program to operate on the entire data continuously.

This can be done by organizing your game objects inside Structures of Arrays (SoA) instead of Arrays of Structures (AoS) and pre-allocating enough memory to contain the expected data.

For example, a simple physics object in an AoS layout might look like this:

struct PhysicsObject
{
  Vec3 mPosition;
  Vec3 mVelocity;

  float mMass;
  float mDrag;
  Vec3 mCenterOfMass;

  Vec3 mRotation;
  Vec3 mAngularVelocity;

  float mAngularDrag;
};

This is a common way way to present an object in C++.

On the other hand, using SoA layout looks more like this:

class PhysicsSystem
{
private:
  size_t mNumObjects;
  std::vector< Vec3 > mPositions;
  std::vector< Vec3 > mVelocities;
  std::vector< float > mMasses;
  std::vector< float > mDrags;

  // ...
};

Let’s compare how a simple function to update object positions by their velocity would operate.

For the AoS layout, a function would look like this:

void UpdatePositions( PhysicsObject* objects, const size_t num_objects, const float delta_time )
{
  for ( int i = 0; i < num_objects; ++i )
  {
    objects[i].mPosition += objects[i].mVelocity * delta_time;
  }
}

The PhysicsObject is loaded into the cache but only the first 2 variables are used. Being 12 bytes each amounts to 24 bytes of the cache line being utilised per iteration and causing a cache miss with every object on a 64 bytes cache line of a Nexus 5.

Now let’s look at the SoA way. This is our iteration code:

void PhysicsSystem::SimulateObjects( const float delta_time )
{
  for ( int i = 0; i < mNumObjects; ++i )
  {
    mPositions[ i ] += mVelocities[i] * delta_time;
  }
}

With this code, we immediately cause 2 cache misses, but we are then able to run smoothly for about 5.3 iterations before causing the next 2 cache misses resulting in a significant performance increase!

The way data is sent to the hardware matters. Be aware of data-oriented design and look for places it will perform better than object-oriented code.

We have barely scratched the surface. There is still more to data-oriented programming than structuring your objects. For example, the cache is used for storing instructions and function memory so optimizing your functions and local variables affects cache misses and hits. We also did not mention the L2 cache and how data-oriented design makes your application easier to multithread.

Make sure to profile your code to find out where you might want to implement data-oriented design. You can use different profilers for different architecture, including the NVIDIA Tegra System Profiler, ARM Streamline Performance Analyzer, Intel and PowerVR PVRMonitor.

If you want to learn more on how to optimize for your cache, read on cache prefetching for various CPU architectures.

Create and manage custom maps in Google Drive

Google My Maps makes it simple to create, share, and publish custom maps online for a variety of business purposes—from publicizing a company’s location to mapping delivery routes and planning events. Now integrated with Google Drive, My Maps allows anyone to easily create maps with custom lines, shapes, and placemarks, to import geographic data (like addresses, places, and coordinates) into maps, and to share maps as they do other Drive files. Shared maps are subject to the same permission settings as other Drive files, allowing Apps admins to decide which groups of employees can share maps within or outside of their domains.



Google Apps admins can turn the My Maps service on or off for their entire domains or specific OUs from within the Admin console (under Apps > Additional Google services). Note that these maps are only available on the web; they can’t be accessed offline and can’t be synced to an individual’s hard drive. As with Google Docs, Sheets, and Slides files, maps do not count toward one’s Google Drive storage limit. Check out the Help Center links below for more information.

Release track:
Rapid release and Scheduled release

Note: all launches are applicable to all Google Apps editions unless otherwise noted

Launch release calendar
Get these product update alerts by email
Subscribe to the RSS feed of these updates

Hilton helps guests book the perfect room with Google Maps APIs



Editor’s note: Today’s guest blogger is Virginia Suliman, Vice President of Digital Design and Development, Hilton Worldwide. Read how Hilton is experimenting with Google APIs to take the guess work out of the hotel booking and room selection process. Hilton is just one of many customers sharing their story as part of our cross-country road trip, Code the Road.

No one likes surprises when they reserve hotel rooms, so it’s crucial for Hilton that people see exactly what they’ll be getting before they arrive. Currently, Hilton’s HHonors guests can use the HHonors website and app as a one-stop tool to control their on-property experience – from finding the best hotels in the right neighborhoods and booking the most suitable one, to soon, using the app as a room key.
couple_sitting.jpg

With a spirit of constant innovation, we’re always looking for new ways to enhance the guest experience. One way we’re doing so is by experimenting with the Google Maps APIs through proof of concept iPhone app functionality we built to enhance the room selection process during digital check-in. The concept tests a the Street View panoramas, part of the Google Maps SDK for iOS, letting users see on the app the exact view they’ll experience when they get to their hotel room. For example, they could virtually look out their window on the app and select the room that overlooks a park or a quiet street corner.
Businesswoman2.jpg

People care not just about the hotel they stay in, but also about the neighborhood, including what kinds of food, entertainment and amenities are nearby. So in our concept, we also tested a controlled list of businesses and points of interest from the Google Maps Places API for IOS to highlight nearby destinations via the HHonors app, like Lincoln Center in New York City, a great fish restaurant in Boston, or the Centennial Olympic Park in Atlanta.

The full potential of Google APIs sets in when you combine them. If successful, the Maps and Street View panorama concepts could one day fully integrate into our HHonors app or global web portal, which already uses Google Maps Business View to offer panoramic virtual tours of our properties to guests.

We believe that happy travelers are repeat customers who become loyalists. If you feel connected to the experience you’ve had with us, you’re more likely to return and to tell others about it. Through technology, we’re hoping to make it easier for people to find the perfect room, have an unforgettable stay and come back for another adventure.

We were delighted to participate in the Code the Road trip. We hosted the Code the Road bus at our Hilton Chicago property on June 10 and are hosting it at Hilton Headquarters in McLean, Virginia on June 22. You can also see the Hilton HHonors app window-view proof of concept demo on the bus.

Making it easier to deliver compelling experiences across screens

Making it easier to deliver compelling experiences across screens
We’ve explained how Programmatic Guaranteed in DoubleClick Bid Manager and Native Ads in DoubleClick for Publishers help ensure your brand shows up in the right place and context. But once you’re present, you have to show a relevant, engaging message to each viewer. Today, we’re excited to launch three new mobile video formats for DoubleClick and a new Creative Preview App, to make it easier to deliver compelling experiences across screens.
Bring interactive video to mobile devices: Video Cue Points component in Google Web Designer
The Video Cue Points component, now available for download, allows developers to build an interactive video ad that looks and feels like VPAID, except that the video runs directly within the display ad on mobile devices. Interactive HTML5 banners with video might take 2-3 weeks of developer time to hand code, but with Google Web Designer and our Video Cue Points component, it can take as little as 3-4 hours.

“Teaser Reels” mobile video component in DoubleClick Studio
With Teaser Reels, you can easily create an HTML5 display ad with an autoplay video teaser. Imagine an interstitial between game levels or directly within mobile web content - a user sees the teaser video automatically and then can click to play the entire video on their device. This will be launching in mid-July, so check back on our help center for more details. (Studio login required)

New mobile in-app templates in Google Web Designer
Our mobile starter templates make it easy to create rich in-app experiences, such as this expandable HTML5 video unit, built by the creative agency Think Jam to promote the release of Warner Brother’s Hobbit film. Learn more about Google Web Designer templates here.

The new Creative Preview App
Once you've built ads specifically designed for mobile, you'll want to preview them across device types to ensure the user experience is positive in every environment and size. We’ve launched the Creative Preview App, now available for Google Play and coming soon to iOS, which allows you to push mobile ads from DoubleClick Studio directly to your mobile device. Now you can preview and test mobile ads in an actual mobile environment. You can also test the exits in your ads to see reporting metrics come through in the DoubleClick Studio output console on your desktop.
We’re working to make the process of building rich, engaging ads for every environment more seamless for brands and agencies, from creative authoring through to delivering the right ad to the right customer at the right time.

Posted by Karin Hennessy, Product Manager, DoubleClick Creative Solutions

How To Setup Enhanced Ecommerce Impressions Using Scroll Tracking

A version of this post originally appeared on Google Analytics Certified Partner InfoTrust's site.
by Nate Denlinger, Web Developer at GACP InfoTrust, LLC

One of our specialities here at InfoTrust is helping ecommerce businesses leverage their web analytics to make better data-driven marketing decisions. This typically starts with installing Google’s Universal Analytics web analytics software and utilizing all of the functionality that is offered with Enhanced Ecommerce tracking capabilities.
Enhanced Ecommerce provides you with a complete picture of what customers on your site are seeing, interacting with and purchasing.
One of the ways you track what your customers are seeing is with product impressions (whenever a user sees an image or description of your products on your website).
Normally, you track what products users see or impressions by simply adding an array of product objects to the DataLayer. These represent the products seen on the page, meaning when any page loads with product images/descriptions, data is sent to Google Analytics that a user saw those specific products. This works well.
However, there is a major issue with this method.  Sometimes you are sending impressions for products that the user never actually sees. This can happen when your page scrolls vertically and some products are off the page or “below the fold”.
For example, lets take a look at a page on Etsy.com:
Sample page on Etsy.com (click for full size)
Here are the results for the search term “Linens”. Currently, you can see sixteen products listed in the search results.  However, in the normal method of sending product impressions, a product impression would be sent for every product on the page.
So, in reality this is what we are telling Google Analytics that the user is seeing (every single product on the page):
Sample page of Etsy.com (click for full-size)

Obviously, no one's screen looks like this, but by sending all products as an impression, we are effectively saying that our customer saw all 63 products. What happens if the user never scrolls past the 16 products shown in the first screenshot?
We are greatly skewing the impressions for the products on the bottom of the page, because often times, users are not scrolling the entire length of the page (and therefore not seeing the additional products).
This could cause you to make incorrect assumptions about how well a product is selling based off of position.
The solution: Scroll-based impression tracking!
Here is how it works at a high level:
  1. Instead of automatically adding all product impressions to the DataLayer, we add it to another variable just for temporary storage. Meaning, we do not send all the products loaded on a page directly to Google Analytics, but rather just identify the products that loaded on the page.
  2. When the page loads, we actually see what products are visible on the page (ones “above the fold” or where the user can actually see them) and add only those products to the DataLayer for product impressions. Now we don’t send any other product impressions unless they are actually visible to the user.
  3. Once the user starts to scroll, we start capturing all the products that haven’t been seen before. We continue to capture these products until the user stops scrolling for a certain amount of time.
  4. We then batch all of those products together and send them to the DataLayer as product impressions. 
  5. If the user starts to scroll again, we start checking again. However, we never send the same product twice on the same page. If they scroll to the bottom then back up, we don’t send the first products twice.
Using our example on the “Linen” search results, right away we would send product impressions for the first 16 products. Then, let’s say the user scrolled halfway down the page and stopped. We would then send product impressions for products 18 through 40. The user then scrolls to the bottom of the page so we would send product impressions for 41 through 63. Finally the user scrolls back to the top of the page before clicking on the first product. No more impressions would be sent as impressions for all products have already been sent.
The result: Product impressions are only sent as users actually navigate through the pages and can see the products. This is a much more accurate form of product impression tracking since it reflects actual user navigation. 
Next steps: for the technical how-to guide + code samples, please see this post on the InfoTrust site.

Some minor DFP API changes related to creatives

Hello, DFP API developers! We just wanted to let you know of some minor DFP API changes that affect all versions of the API. Most likely these won’t affect your integration with DFP, but we’re announcing them here for transparency.

Deleted line item creative associations (LICAs) are no longer persisted

Deleted LICAs are no longer persisted in the product. This will affect all versions of the API. There are two things to be aware of as a result of this. First, the method getLineItemCreativeAssociationsByStatement will no longer include these deleted LICAs. Second, if you’re syncing your LICAs daily, you may notice fewer LICAs coming back. As a reminder, you can always use the action DeactivateLineItemCreativeAssociations if you want to keep them around, but not use them. This change is already in effect.

Creative placeholders are no longer assigned an ID

We are also getting rid of CreativePlaceholder.id because it is not used or referenced anywhere in the API. This field will be removed in v201508. For all versions prior to v201508, this ID now comes back as 0, instead of an ID assigned by Google. This change is also already in effect.

If you have any concerns or questions about these changes, you can always contact us on the DFP API forums and we’ll be glad to help you out.

Making it easier to deliver compelling experiences across screens


We’ve explained how Programmatic Guaranteed in DoubleClick Bid Manager and Native Ads in DoubleClick for Publishers help ensure your brand shows up in the right place and context. But once you’re present, you have to show a relevant, engaging message to each viewer. Today, we’re excited to launch three new mobile video formats for DoubleClick and a new Creative Preview App, to make it easier to deliver compelling experiences across screens.
Bring interactive video to mobile devices: Video Cue Points component in Google Web Designer
The Video Cue Points component, now available for download, allows developers to build an interactive video ad that looks like VPAID, except that the video runs directly within the display ad on mobile devices. Interactive HTML5 banners with video might take 2-3 weeks of developer time to hand code, but with Google Web Designer and our Video Cue Points component, it can take as little as 3-4 hours. 

“Teaser Reels” mobile video component in DoubleClick Studio
With Teaser Reels, you can easily create an HTML5 display ad with an autoplay video teaser. Imagine an interstitial between game levels or directly within mobile web content - a user sees the teaser video automatically and then can click to play the entire video on their device. This will be launching in mid-July, so check back on our help center for more details. (Studio login required)

New mobile in-app templates in Google Web Designer
Our mobile starter templates make it easy to create rich in-app experiences, such as this expandable HTML5 video unit, built by the creative agency Think Jam to promote the release of Warner Brother’s Hobbit film. Learn more about Google Web Designer templates here

The new Creative Preview App
Once you've built ads specifically designed for mobile, you'll want to preview them across device types to ensure the user experience is positive in every environment and size. We’ve launched the Creative Preview App, now available for Google Play and coming soon to iOS, which allows you to push mobile ads from DoubleClick Studio directly to your mobile device. Now you can preview and test mobile ads in an actual mobile environment. You can also test the exits in your ads to see reporting metrics come through in the DoubleClick Studio output console on your desktop. 
We’re working to make the process of building rich, engaging ads for every environment more seamless for brands and agencies, from creative authoring through to delivering the right ad to the right customer at the right time. 

Posted by Karin Hennessy, Product Manager, DoubleClick Creative Solutions

Accept or reject external guest requests to join Hangouts video calls with the Hangouts iOS app

We recently completed the cross-platform rollout of a feature allowing Google Apps customers to share links to Hangouts video calls so that external meeting guests may request to join if not explicitly invited. 

Previously, video calls shared with the link required someone in the Apps domain of the Hangout video call to accept those requesting access on the web. With today’s launch, we’ve enabled this accept or reject functionality in the latest version of the Hangouts iOS app.

To accept or reject a request to join a video call on your mobile device, tap the ‘Accept’ or ‘Decline’ button in the pop-up screen that appears when a guest is requesting to join.
This functionality is coming soon to the Hangouts Android app.

Release track:
Rapid release and Scheduled release

For more information:
Help Center
Get the latest Hangouts app in the App Store

Note: all launches are applicable to all Google Apps editions unless otherwise noted

Launch release calendar
Get these product update alerts by email
Subscribe to the RSS feed of these updates

Launceston looks forward (again)

Launceston has always been a forward-looking town. It was the first town in Australia to be lit by hydroelectricity (and the first town in Australia to have underground sewers!). It was also a regional winner of our 2013 eTowns Award, and Launceston small businesses have been quick to see the potential of the web to help them grow.

We recently asked more than 150 small business owners in Launceston whether they thought the Internet would be important to their future growth - and 100% said yes. However, around one third of those business owners also said they didn’t know how to take advantage of this.

So we were delighted to visit Launceston today as the fourth stop on a nationwide roadshow (and that’s not just because of Tasmania’s delicious cheese!). The roadshow, in partnership with the Australian Chamber of Commerce and Industry is part of our efforts to help small business around Australia make the most of the web.
Chilly conditions relieved by a warming coffee at our Launceston roadshow this morning 

Our guest Eric Hutchinson MP opened the event for around 120 Launceston small business owners, who then heard how the web could help them find new customers and grow their business. We heard from Lisa Tedeschi, the owner of fashion store Sebachi, who has used AdWords to market her clothes store not just to people in Launceston, but all over Australia. She told us how the Internet had helped her start exporting clothes overseas, to locations as far afield (and fashion-forward!) as Sweden and Belgium.

Sebachi owner Lisa Tedeschi at the Launceston roadshow today 

Lisa’s success is also Australia’s success. Research shows that businesses that are online are twice as likely to be growing and four times as likely to be hiring staff. So it’s vital for Australia that we support small businesses as they look to get online. The good news is that it only takes a few minutes, and you don’t even need a website to start off. To find out more about our free tools, have a look at Google My Business.

Posted by Richard Flanagan, Head of Small Business Marketing, Google Australia

Publish Google Sheets spreadsheets in five additional formats


In Google Sheets on the web, if a person wants to make a spreadsheet available for a large audience to see, they can publish the file as a web page. Once that file is published, the person receives a URL that can be sent to whomever they choose or embedded into a website. Today’s launch allows people to publish spreadsheets in five additional formats—as comma-separated values (.csv), tab-separated values (.tsv), a PDF document (.pdf), a Microsoft Excel® spreadsheet (.xlsx), or an OpenDocument spreadsheet (.ods). The URL generated, when opened in a browser, will automatically download the spreadsheet in the chosen format (spreadsheets in these additional formats cannot be embedded).
More Publishing Formats.png
Try out this new feature in Google Sheets on the web today.

Release track:
Rapid release and Scheduled release

More information:

Help Center

Note: all launches are applicable to all Google Apps editions unless otherwise noted

Launch release calendar
Get these product update alerts by email
Subscribe to the RSS feed of these updates