Google’s new Play Store algorithm to halve size of updates

[Spiderloser]

Google’s new Play Store algorithm to halve size of updates

 

Quote

The amount of data required for updating Google Play apps can really send your mobile bill through the roof, especially if you aren’t using Wi-Fi. Fortunately, your concerns have been heard. Originally created by Colin Percival, Google has rolled out a new Delta algorithm, bsdiff, which reduces the app update size and lets you save on the data required for updating them.

Quote

This new algorithm does this by further compressing the size of patches for apps and games. According to a blog post by Anthony Morris, SWE Google Play, for about 98 percent of app updates from the Play Store, only deltas to APK files are downloaded and merged with the existing files to reduce the size of the updates. Now, Google’s new algorithm will further reduce the patches by up to 50 percent. As he explains in the post,

 

My Thoughts: Sounds cool if it works wonder if there wil anyl be problems with the apps tho 

 

Source : http://www.androidauthority.com/googles-new-play-store-algorithm-halve-size-updates-705575/

[Guest]

"algorithm" they basically just compressed the apps, like what steam was doing already.

[thekeemo]

Quote

Binary diff/patch utility

bsdiff and bspatch are tools for building and applying patches to binary files. By using suffix sorting (specifically, Larsson and Sadakane's qsufsort) and taking advantage of how executable files change, bsdiff routinely produces binary patches 50-80% smaller than those produced by Xdelta, and 15% smaller than those produced by .RTPatch (a $2750/seat commercial patch tool).
These programs were originally named bdiff and bpatch, but the large number of other programs using those names lead to confusion; I'm not sure if the "bs" in refers to "binary software" (because bsdiff produces exceptionally small patches for executable files) or "bytewise subtraction" (which is the key to how well it performs). Feel free to offer other suggestions.

bsdiff and bspatch use bzip2; by default they assume it is in /usr/bin.

bsdiff is quite memory-hungry. It requires max(17*n,9*n+m)+O(1) bytes of memory, where n is the size of the old file and m is the size of the new file. bspatch requires n+m+O(1) bytes.

bsdiff runs in O((n+m) log n) time; on a 200MHz Pentium Pro, building a binary patch for a 4MB file takes about 90 seconds. bspatch runs in O(n+m) time; on the same machine, applying that patch takes about two seconds.

Providing that off_t is defined properly, bsdiff and bspatch support files of up to 2^61-1 = 2Ei-1 bytes.

Version 4.3 is available here with MD5 hash e6d812394f0e0ecc8d5df255aa1db22a. Version 4.2 is available in the FreeBSD, NetBSD, and OpenBSD ports trees as misc/bsdiff, in Darwinports as devel/bsdiff, and in gentoo as dev-util/bsdiff. It has also been made into a Python extension module, and there is a Windows port available.

The algorithm used by BSDiff 4 is described in my (unpublished) paper Naive differences of executable code; please cite this in papers as

Colin Percival, Naive differences of executable code, http://www.daemonology.net/bsdiff/, 2003.
A far more sophisticated algorithm, which typically provides roughly 20% smaller patches, is described in my doctoral thesis.

http://www.daemonology.net/bsdiff/

[laminutederire]

21 minutes ago, spidsepttk said:

"algorithm" they basically just compressed the apps, like what steam was doing already.

Not really, steam updates don't compress things, they only download what is different, like with version control tools by the way.

[Guest]

Just now, laminutederire said:

Not really, steam updates don't compress things, they only download what is different, like with version control tools by the way.

not steam updates, when you download a new game it downloads compressed than takes a few seconds to uncompress the game once it is finished downloading.

[laminutederire]

Just now, spidsepttk said:

not steam updates, when you download a new game it downloads compressed than takes a few seconds to uncompress the game once it is finished downloading.

Yeah but Google play doesn't seem to do that as well..

Steam compression isn't perfect , it isn't 50% of total size. Well it is on older games, but you gain less that 5GB on more than 60GB of files for GTA V for instance. It just compresses the game engine I think..

[Guest]

Just now, laminutederire said:

Yeah but Google play doesn't seem to do that as well..

Steam compression isn't perfect , it isn't 50% of total size. Well it is on older games, but you gain less that 5GB on more than 60GB of files for GTA V for instance. It just compresses the game engine I think..

Wow, that sounds like a stupid move from steam, surely they could just compress every file in the game than make us spend a minute uncompressing once it is done, or even uncompress while downloading.

[laminutederire]

Just now, spidsepttk said:

Wow, that sounds like a stupid move from steam, surely they could just compress every file in the game than make us spend a minute uncompressing once it is done, or even uncompress while downloading.

Well lossless video or image compression isn't necessarily that easy to do in a practical manner

[LAwLz]

5 hours ago, spidsepttk said:

Wow, that sounds like a stupid move from steam, surely they could just compress every file in the game than make us spend a minute uncompressing once it is done, or even uncompress while downloading.

A huge chunk of data in games are textures, video and sound files. Those are usually already compressed so it becomes very hard to compress them even more.