scala.bythebay.io: Hunter Payne, Numbers every Scala Programmer should know
Recording: scala.bythebay.io: Hunter Payne, Numbers every Scala Programmer should know
so I was inspired to create this talk by uh a wonderful talk done by Jeffrey Dean of Google which was sort of a history of Google and Google's infrastructure and how it evolved over time towards the end of the talk uh there was a very good slide that was shown uh that had the title every uh numbers every programmer should know uh s spond a website that that keeps track of these numbers over time um I really love this slide because it uh explained uh very simply a concept I had a hard time explaining to other programmers um so I decided to sort of make this talk to sort of take those numbers see how we apply them in software and how we can uh sort of extend that concept to more uh more specific needs so the original slide looks something like this um as you you can see it's a bunch of common things that you that happen in a computer program uh cash hits and cash misses locking things copying things to and from pieces of memory my personal hypothesis about why this slide arose was that there was probably a discussion between two Engineers uh about these two these two parts of the slide right here uh there was probably somebody that uh wanted a a particular service to compress its data on the way out and there was somebody else that argued that hey that's going to be too slow that's going to slow down my service and this is how they sort of settled that argument the interesting thing in this case is that today's answer the answer uh when they originally had the argument was to not compress or to compress and today uh it turns out that that's no longer the case so this is an interesting case where the evolution of Hardware has changed the correct answer so to speak from a performance point of view um but if you look up it down you see a lot of common things that you'll do inside of a computer program uh you'll see accessing dis here you see compressing things here um and down at the very slowest as always is going around the world on the network and so what did the numbers tell us um they tell us that CPU and RAM is very fast that locking tends to be very fast uh networking side the data center is amazingly fast um not so a few years ago but uh they've done a really great job improving uh back planes uh and routers to make them go very very fast copying data is is still a little slow but it's still still pretty fast um discs are slow but you know they're getting ssds are less slow uh and anytime you go around the world or anytime you go from data center to data center it's always very slow so just like Big O notation you use to analyze algorithms you can do the same thing with performance programming um you can look at the most expensive operation that you are using in a particular algorithm or service or across your hold infrastructure and do the same sort of complexity analysis on that that that you would do on uh in an academic uh exercise so let's go back and look at the numbers again uh I think the most important column to look at is over here on the exponent um that sort of groups together operations into clumps or clusters that generally operate at the same speed um so you got uh notice locking is up here um and that's all in the first order of magnitude um other things are slower accessing dis is way down here in the third and fourth one um accessing the network at large very very slow so um inside a computer I tend to look at a computer roughly like this um some of you more clever folks out there will notice that this isn't exactly accurate um the inaccuracy is roughly here uh that should have labeled that North and Southbridge um but the more important concept I'm trying to illustrate here is that everything that runs fast runs inside the CPU when the CPU when you have to access Hardware outside the CPU it's necessarily slower and this includes Ram um Ram is still very very fast but and it's far faster than say accessing you know discs over here or accessing your your network um but still it you pay a cost for it uh and the speed of a lot of algorithms is very much governed by what level of the cash you're accessing or how far down the cash hierarchy you're actually needing to use to perform your work so let's talk about how the this impacts this this knowledge impacts how we design an entire infrastructure for a second um so first you have to talk about what is fast what does it mean to be fast um there's two basic ways that you look at fast uh there's latency and there's throughput um latency is basically the amount of how fast your car is going on a highway throughput is how wide that highway is uh and often when you're designing a particular piece of software inside your infrastructure you really need to know are you going for latency or are you going for throughput now it's important to note when you measure latency you generally measure latency at a particular level of throughput so how fast am I responding when I'm getting a th requests per second um because that that profile is going to change as you get higher loads or lower loads um so it's important to know what what how much traffic you're handling at a particular level of latency uh throughput is generally just measured just all out whatever throughput you can get uh doesn't matter how much you're sacrificing latency so I tend to think of these things as either the speed of the car or how wide the the the highway is and so that that gives rise to two basic patterns that you see in modern infrastructures U microservices which have been very popular for a long time uh 5 to 10 years or so um people don't often know exactly why they're building microservice architectures um the short answer is is to squeeze latency because latency is how fast you're responding to users and that is how how good your response rate is which ultimately theoretically should lead to more Revenue um you generally not every part of your infrastructure is responding to a human scale request so some things like uh the metrics you're Gathering those things will be coming in and you don't really care there's no response that's happening there um in those cases you're really not going to worry so much about it you're just going to be optimizing for throughput so why do you do a microservice well as I said before you do it for latency um generally this is going to be responding to a web request there's two basic scales for for latency there's human scale and there's machine scale so human scale is anything that a human can notice right so under 100 milliseconds or so no human no humans just don't operate that quickly so as long as you're going that fast it's good enough um the other one would be machine scale so that's us generally used in finance or high frequency trading something like that where you're trying to beat another programming team that's a whole different ball game um and generally you're going to write the code differently based on what you're doing the uh other advantage of microservices is it's nice to break your teams into smaller and smaller groups if you have a particular team that's only operating for five Engineers it's a lot easier to manage when than when you have 40 or 50 engineers so as opposed to data pipelines uh applications that are designed to move as much data as possible through some section of your infrastructure so when you write those you're generally writing them differently um you're generally going to uh determine a certain batch size certain number of requests that you're going to handle it once you're going to pre-allocate all the resources you need to process that particular group of rows uh and then you're going to execute them in those groups uh this gives you a little bit simpler architecture um you can get it to go a lot faster uh and you operate the machines differently so in a microservice you're offer op you're often operating at 30 to 50% load for the for the servers well for these machines you're going to operate them all the way hot 100% so there's when I'm looking at uh choosing a particular platform uh I generally look at three different aspects of that platform um the first one I always look at is reliability um so that is basically whether how often you're processing a row or How likely you are to process a row are you guaranteed to process it once are you guaranteed to process it at least once are you guaranteed to process it at most once um generally a system in a particular configuration will give you some guarantee and you need to identify beforehand what guarantee you need um because it's very difficult to make a system that doesn't give you a guarantee give you a guarantee um that's that's particularly difficult the other aspect of reliability I look at is something known as the cap theorem cap the theorem was first stated by a guy named Eric Brewer who was a uh uh PhD candidate at Berkeley at the time uh and he basically stated that you get two of the following three you get consistency availability or partition tolerance just like in uh most areas of work good fast cheap pick two well in this case consistency availability partition pick two so you have to decide which of these things you're going for which of these things that is uh important to you because you're not really going to be able to make up the third one if you wanted availability and you didn't choose it you're not really going to be able to add it yourself not without significant time effort pulling out of hair blood whatever the second one I look at is durability and this is basically the ability of the system to function corly as long as the hard dis don't fail so if you get crashes what have you the data will still be there um so this is generally given to you by a database something that's that's asset compliant um if you need this it's better to just have a system that gives it to you it's very hard to build in yourself and the third one I look at is scalability which is the ability of the system to handle more traffic with more Hardware um generally in a scalable system when you're trying to go for very large scale you'll have some sort of controller node involved there in kof's case that would be zookeeper something that's managing the metadata of the system um there's generally a one or a smaller number of those nodes that are handling that work and generally at the highest levels of scale that is what's going to Define how fast that system can run um sometimes you'll see three level systems generally no uh not unless you're working for Google or something like that so let's talk a little bit more about cap uh analysis and the cap theorem um so you have uh availability and consistency that's the most common pattern that you see that's certainly the oldest pattern that you'll see um traditional RB rdbms's do this um you typically see these in e-commerce applications other web applications things that need to provide om um this is the most common pattern that you'll see um the second one is availability and partition tolerance those are sort of the Dynamo descendants Cassandra cdb um those are for when you want the system to always be able to read data or always be able to write data you always want the DAT the data to keep flowing in no matter what's happening that's really what that's really what you get with these kinds of systems um the final one is consisting partition tolerance you typically see these in financial transaction applications these are systems that will refuse to accept new data if something's wrong with the cluster these are systems that are designed to fail rather than let you do the wrong thing so when you're choosing uh a third party application to use whether it be an open source or a software vendor it's all about trade-offs if you don't if there's a particular requirement you don't know about ahead of time this can significantly throw a monkey wrench into your plants because it's very difficult to take a system that's AP and make it ca um this is probably going to be harder than the rest of the work you have on whatever project that you're working on uh so it's better just to choose a system that actually can do this out of the gate uh and it's all about trade-offs there is no perfect system there is no system that's better than the rest there's a there are simply systems that give you particular guarantees and those are the that's what those systems do and adding extra guarantees to those systems is significantly difficult so it's important to note what use case the platform was written for because when you're writing a platform like that there's a thousand decisions that are going through programers heads they're trading off you know how reliable is logging versus what should happen in this failure case or that failure case or what have you um and they'll generally have a use case in their head they're writing it for um so you can't really take a system that's designed to be an ETL system and turn it into a really scalable analytic system you can't really take an analytic system and turn it into a ETL system because they were designed for different things and tiny little things like how they handle errors how they handle recovery recovery those sorts of issues they just just will not be done in the way that you expect them to be done or need them to be done if it was written for use case a and you need use case b so it's also important to note does it use disc does it use networking that'll give you an idea what its maximum scalability is um and does it give you the one toone guarantees you need or do you need just more statistically correct uh guarantees so how do we use the numbers so let's talk about one particular use case here um let's imagine a example application very simple application um something that simply takes uh Json objects via rest API it parses the Json does a bit of transformation on it and then sticks it into a database so say we write this it works wonderfully we put it in production and we're ready to go ahead and use it we turn it on it does okay but it doesn't scale and perform as well as we wanted to what part of the software should we optimize does anyone know any guesses which would [Laughter] be uh that's close to correct yes uh we'll we'll that's pretty that's pretty close to correct actually so let's do a little bit bit of uh back in the envelope math um so a uh a 40 gig network will run at 5 gbt a second theoretically but in practice it'll run more like a gigabyte per second um so assuming we're using the network for both the in and the out we're reading in HTTP writing out jdbc so we're using both well that means that this network in stack can handle about quarter million 2 K Json objects a second roughly um do a little bit more math uh 40 core box uh 2K parsing a 2K Json object can do about 30,000 objects per core per second so a 40 core box can do about 1.2 million per second so optimizing the parsing or transformation doesn't really do us much good because the thing that's slowing us down the thing that's bottlenecking us is our networ performance so the correct answer in this case would likely be to compress the Json on the way in which brings us back to the original numbers so now let's talk a little bit about blocking versus non-blocking it was the same it was the same decision that the original people that created the chart were going through whether do compression or not on the network anyway um blocking versus non-blocking IO uh I know a lot of folks love non-blocking IO uh it certainly makes you sound smarter um it's uh it's it's it's more interesting to write it's much more efficient um but it's not always better uh sometimes it's worse this is one of the things that surprised me greatly these two bars here that's blocking performance these two bars here that's non-blocking so in some used cases non-blocking is not just slower we're talking about that's a logarithmic scale that's 100 times 100 times slower um but when you get up to real world levels of traffic over here they're roughly the same except for blocking right strangely it's much faster than everything else um but this isn't this doesn't mean you should take your application at home and switch to block it that's clearly not the case this was a micro Benchmark it got to use all all the available resources on the box it used a lot more CPU when it was doing this blocking iio it was also writing to a fixed number of file handles so it was sort of optimized for blocking uh sort of cheated a little bit um this is the best case for blocking but generally it won't be the case that uh you should use blocking so when should you use one versus the other well uh it depends on how many uh IO resources you're hand how many handles you're you're uh interacting with um which is basically how many sockets you're inter interacting with or how many files you're interacting with if you're interacting with a very large number of them you definitely want to use non-blocking IO the extra overhead of having those threads blocking and waiting to access those file handles would be much slower so it would definitely be more effective in cases where you're say writing to 40 different sockets or hand handling 40 different clients that's going to be way better than non-blocking um but if you're doing a batch application you're writing one file as fast as you can well then you just use a very simple blocking API and the reason for this is that down at the very lowest level of the stack uh all IO is is asynchronous downside the the kernel of the operating system um and so the blocking apis there's extra code written by System programmers to give you blocking semantics and those guys this is all they do somebody sent sat for a year optimizing the blocking code inside Linux and they were really smart and really good at it uh it's going to be very difficult for you to achieve that yourself um and they did that for a very specific reason they did that so that when you're writing out one file you can do it as fast as possible so that's what really blocking is for when you're writing one file you're talking to one thing on the other end of the network so I did some more benchmarks for this presentation sort of additional numbers that should sort of inform this the core idea I'm going to keep hammering home in this is this uh performance is about measurement all right whether that's profiling or micro benchmarks which is what I did it doesn't matter but it's all about measurement the hardware will change over time and the performance benchmarks will change over time so I'll give you an example used to be that matches well it's still the case that a match will compile in and call a method they called is instance of is instance of used to be the bane of java programmers you should never ever call it in addition to the fact that it's not very o uh you shouldn't do it because it's very slow Well turns out that's not really true anymore used to be true I thought it was true when I started writing this presentation turns out I was very wrong turns out that is instance of is now nearly as fast as an integer comparison which surprised the heck out of me I was amazed so those guys are very smart on the uh Oracle um jbm team and they did a really good job with it uh and I didn't even think it was possible to make it that fast but they did um and the only way I found this out is by measuring it I I didn't spend my time digging through this the code of the jvm but I did go in and measure it anyone can measure it you don't have to be especially great engineer to measure it uh and then you can learn you know what technique you should use so it turns out because they did this that the match statement is incredibly fast um it used to be the case that uh you this was it was good to do some sort of weird uh compiler tricks to make it so that when you were matching on a on a class you weren't actually there's actually a Json scholar library that does some very clever uh compiler tricks to sort of avoid this um that will go un named uh and it gives you some pretty awful compiler errors when you mess up the code uh or when you import the wrong thing is quite frustrating at one point that was really an excellent optimization technique today it's just pointless um some of the other things on here are generating random numbers and getting current time turns out they've gotten very fast the Linux test calls are very fast nowadays um down here this is constructing a case class with four arguments um that's actually kind of slow especially when you compare it with how fast a lock is you would have to contend for a lock a lot to me make it so that copying data is faster than locking uh interacting at with the file system is the next level so that's a little slower here's a context switch which is roughly as fast as interacting with the file system that should sort of let you know how expensive uh Contex switches are uh and then down here at the bottom some interactions with various uh data data containers um you should see that uh map is incredibly fast we would expect to be incredibly fast array is pretty good but it starts to fail when you get that this many elements so it doesn't go quite as fast but it's because it's so memory efficient it does pretty well and list is so slow that you shouldn't even bother with it not if you have a lot of pieces of information in there so let's talk about a couple other programming techniques um let's talk about recursion in Loops now uh I measured uh while Loops versus four comprehensions versus recursion versus tail recursion so it turns out that W loops and four loops and and tail recursion all roughly the same speed when you have small numbers of elements but this might come as a surprise to some of you all that it turns out that while Loops are significantly faster in very large numbers of iterations about 30% faster in fact so I know some of you functional lovers out there will would rather lose a finger than write something like a wild Loop but uh when you're on the inside of your inner loop and you're trying to squeeze every last microsc of latency out of there you might want to think about switching a four comprehension to a wild Loop especially in a loop where you have a lot of things you're iterating over if you're looping over that many many times now it's also important to note that I measured these with Scola 211 I might be wrong Scola 212 has come out they might have made made four comprehensions faster so somebody might take the code download it run it on scholar T2 and come out with turns out four comprehensions are now just as fashion as W Loops at which point my advice now is useless but until somebody measures it nobody knows so uh caching is another useful technique caching is almost always a good idea the only time caching is not a good idea is when it's going to fill up a particular level in your CPU cache so if for instance you fill up all of L3 and you can't even fit the cach into L3 caching is not going to work in those cases but that's very rare and you know generally you're not going to worry about it too much caching is almost always a good idea um talk about different collections we measured a array and map and sequence and index sequence we didn't measure list because it was so slow um the thing to note is that because array uses less memory it's actually faster than map for small numbers of elements um something less than 500 or a th000 elements in your list you should use array all the time and if it's bigger than that you should use map all the time um turns out those are the fastest data data structures um the only time that's going to be not the case for a larger larger data structure is there will be cases when array fits in one level of the CP cache and the map doesn't because it takes twice as much memory in those very strange very rare cases array will even be faster than map but that's not going to happen too often so the final one we'll talk about is mutable versus immutable so I know everyone loves immutable data structures they're easier to program for U but it turns out that mutable inserts are 30% faster um surprisingly immutable removes are faster than mutable removes it's very weird um but generally you want to use the the the lesson I drew from this is that you want to use mutable day structures when on each request on in you're generally going to do one right to The Container so if for instance you're going to end up doing something where you rebuild a cache and you do 5,000 wres and then you do 10 million reads use immutable well you're going to use a builder in that case anyway which is still a mutable data structure but you know at the end rrap it and immutable and that will be all will be good um but in the case where you're sort of you're doing an lru cache and you're moving things from the cache as you're inserting into the cache um in those cases it's probably better to use mutable um you know another thing to consider is the type safe folks are very smart they're very good programmers they don't have a lot of resources they spent a lot of time writing the mutable data structures they did that for a reason the reason is this particular use case where you get a read and then you do a write and then you do a read and then you do a right that's when you want to use mutable and the final concept we'll talk about today are inter Loops so not all lines of code are run the same number of times some of them are run um generally you'll have a a basic pattern software you have some initialization you have some tear down code at the end and in the middle you have code that's run over and over and over again um that's the inner loop uh the truth is that a database is the ultimate example of this in a database about 90% of the code only runs when the query is executed not on every row inside the database uh 90% of the code all it does is try to figure out the exact fastest most sophist most efficient way of processing individual rows inside the database uh from the table uh and they basically spend 90% of the time writing code that doesn't run per Row for the the data that's coming out of the database or the data that's going into the database for that matter um this is basically what you'd expect from 40 Years of optimizing one architecture so so let's talk about how you uh how you might optimize a particular inter Loop uh one technique is splitting an interloop into two of them uh if you have an interloop that uses a lot of memory uh it might be better to do this because you can fit uh more rows in cash um you want to amortize expensive CIS calls um maybe you're creating files or something else that's rather expensive you want to try to do that once at the top of the loop and just reuse that handle if at all possible um you want to remove ifs and uh non-inline function calls uh to figure out if something's not- inlined you sort of need to use Java p and some other fancy tricks um consider using a API for parsing that does callbacks instead of giving you a Dom the Dom uses a lot of memory callbacks are just going to use as much memory as they need to perform that particular call back and then free that memory or reuse that memory um they're generally a lot more efficient um and then you want to hoist Constance and static computation out of that Loop um the compiler will hoist simpler things for you but there's only so much it can do um so how does this help us design software well the first thing is you need to understand what you're doing are you doing high throughput or you doing low latency so that's going to inform what platforms you're going to use what libraries you want to use um cach when possible you use array for large corre use use map for large collections use array for small Collections and you only want to bother with optimizing the inter Loop uh the final thing is your Hardware may be different from mine so if you don't believe a number in here or you think it's different maybe it is Rerun it on your Hardware find out let us know we're going to keep those numbers up up to date um it's uh we are sharing it on GitHub right there uh and uh send me a are if you uh don't like how I wrote some of the code anyway thank you for your time [Applause]