Domain Modeling For Better Contracts

In the post about communicating contracts through enforcing endpoint contracts, we took a look at some basic types which are available in Signet. Today we are going to talk about how to add more information to your types by creating your own data types.

Last week we took a look at how to build types as sets with characteristic functions. This week we will apply that information in order to add extra information to our types.

By this point I’m certain there are plenty of people who are thinking I’ve gone completely off the rails. Javascript, after all, is a dynamically typed language. Don’t burden yourself with all of this type stuff and just write some code!

Although this is true, most people view types as a constraint which only causes pain. Though this might be true if you are coming from a language like Java which contains lots of artificial constraints around type creation, and after all is said and done, the types are still weak and restrictive.

On the other hand, if we consider types as a way to add a layer of correctness checking and a tool for communicating with others, types become less a restriction and more a tool we can use to make our programs better. Good types will make a program transparent and predictable. These are traits we definitely want in our programs.

Just as a refresher, let’s have a look at where we left off with our purchase API from the enforcing endpoints blog post. This way we have a common position to understand where we started and where we’re going.

Now that we have our API defined with regard to basic types, we can start to ask more meaningful questions. Instead of asking things like “what does this function do,” we can ask directed questions to inform our programming better: What kind of numbers are they? What is in the array? What kind of argument must the function take?

The last two questions are easiest to answer since we don’t have to look any farther than higher-kinded types. This is, of course, scary sounding the first time you hear it. I had no clue what a higher-kinded type was the first time I heard the word. Fortunately, many of you may already be familiar with them even if you don’t know the word. Java and C# both support higher-kinded types.

Higher-Kinded Types and You

First and foremost, let’s discuss what a higher-kinded type actually is. (It’s a type.) Once we have a better grasp on that, we will use it in code to make everything a little more clear.

A higher-kinded type is simply a type which takes a type as an argument and returns a type. I know, that sounds weird. How does a number take a string and return a type? I asked the same thing.

It turns out, however, that it’s not nearly as foreign as it might seem. One very common type we rarely think about in Javascript which could easily be handled as a higher-kinded type is an array. An array is, itself, a type, but it contains values which are also typed. This means, if we had a language to express it, we could declare an array which contains only a single type.

As it turns out, there are potentially infinite different types which are, or could be, higher-kinded. In this post we are going to look at just two: array and function. With the type signature language available with signet, we can explicitly declare an array type as needed. This means we can do things like the following.

We can see both of the tested arrays are completely valid Javascript arrays, but the second is not an array of exclusively numbers. There are ways we could create an array which would support numbers and strings, but that’s beyond the scope of this post.

Just like we can declare information about arrays, we can also say something about the expectations around a function. Instead of simply saying a value is “function,” we can actually say a value is a “function which takes a number.” In much the same way we declare our types in arrays, our function type declaration is “function.”

Now that we have an expanded type language to draw upon, let’s update our API and clarify the communication of our domain model.

Subtyping With Characteristics

Now we just have the ‘number’ type scattered everywhere throughout our code. Although this is better than nothing, it would be SO MUCH better if we actually knew something about those numbers. What do they mean? How are they used? What are the constraints?

It turns out we have just the thing to remedy this pain, it’s called characteristic functions. As we know from our earlier discussions on characteristics, we can add richness to our type system through set-describing predicate functions. (Protip: all predicates describe sets)

Before we dive into creating new types willy-nilly, let’s take a moment to account for the different number types we have. By properly identifying the actual domain language we care about, we can create better types which will allow us to clearly describe our application to people who might know nothing about it.

Ultimately, we care about tax, price, amount of tax to pay (tax amount) and purchase total. If we were to simplify this list a bit, we can identify a couple of distinct bits of information.

First let’s consider tax. Tax is a percentage amount. Since, where I live, taxes are always greater than or equal to 0%, but always less than 100%, I am going to say tax is a percent value which will always fall between 0 and 1. For example, in San Diego, sales tax is currently around 8% or 0.08.

Now, we can take a look at price, tax amount and purchase total. Each of these is a value which is related to a value an amount our customer will be paying. This means we can roll these all into some aspect of price. We will say a price value will be greater than or equal to 0. This describes our data pretty accurately for the moment, so let’s go with that.

With our base types sorted out in a way we can jump off from, we can start building characteristics. By clearly defining our characteristics, we give our new types programmatic meaning. Let’s see what our basic characteristic functions will look like for price and percent.

The other piece of this puzzle is, we need to register our types with Signet. Fortunately, this is a simple process. We know that each of these types is actually a number, so we can simply use the subtype function and declare these two functions as new types, inheriting from number. This is also why we didn’t need to test each value to see if it is a number, our subtyping will guarantee we only verify numbers.

We can use our price type to create our other two types by simply aliasing them and using the price definition to ensure our data constraints are clear.

Let’s have a look at our updated API and see how our types are coming along!

Duck Typing our Object

At this point, our API is pretty clear, but there is still one last type which just doesn’t quite convey the information we want to know. Our array of purchases is still described, simply, as an array of objects. This could be much better, if only there were a way to check it.

As it turns out, the Go language has popularized the notion of object similarity through duck typing and that is precisely what we are going to do here. If we know enough information, we can tell whether our object satisfies the Liskov substitution principle, and can be used in place of our intended object.

Signet provides a means to perform duck typing as well, so we don’t have to build our characteristic function from the ground up every time, because that could end up being a LOT of repeated code. Let’s build a duck typing characteristic and finish up our API types.

Now we have a name for our purchase object type, which means we can easily check whether our array of purchases actually adheres to our expectations. Plus this will provide a way for others to understand what we intended when we wrote the code, making it much easier to write new code against the existing API.

Wrapping Things Up

Although this just scratches the surface of using types in your program, hopefully this exercise helps you communicate intent and define a clear domain model. By taking core types we already know and applying a small amount of predicate logic, we surface a new way to talk about our program and the data we use.

Instead of simply using old code as a reference for what it does, add a little annotation, a little bit of logic and get a lot more bang for your buck. In the end, types don’t make everything correct all the time, but they do a lot to make you and others like you a lot more awesome!

Comments Off on Domain Modeling For Better Contracts

Objects Are Still Shared State

Dear programmers coming from Classical Object Oriented programming, please stop thinking that encapsulation of variables eliminates the “globalness” of your variable. It’s a hard truth, but you had to hear it from someone; you have a problem. Consider this an intervention.

I had a conversation a couple months ago where I looked at some code a senior developer had written and asked, “why are you using a global variable?” The response I got was “it’s the exposing module pattern, so it’s local and encapsulated. It’s not global.” The variable was a cache object exposed outside of the module; and it was global anyway.

When I say global, it is not about whether the entire program, or the entire world, can access your value, it’s about how your variable gets managed and modified. Really, the problematic aspect of a global variable comes from the fact that global variables, in many popular languages, represent shared, mutable state.

Consider a world where every variable is actually immutable, i.e. once you create a variable, you can’t change the value. In this particular case, a global variable is really nothing more than a globally readable value. You can’t write to it, so you can’t impact the rest of the running program. Is that global variable actually a problem? Decidedly less so, that’s for sure.

Mutating Object State

Let’s take a look at a very simple, though rather common, example of the way variables are often managed inside objects.

There are two things wrong with this if value is actually important to the internal state of the object. First, since Javascript does not support private variables (explicitly, but we’ll come back to that), then this suffers from the Indecent Exposure code smell. Essentially, anyone in the world can directly access and modify the internal state of this object. That’s bad news.

The second issue with this object is the getter actually modifies the internal value of our object and returns a representation of the previous object state. Effectively, our getter is modifying the internal state of the object and lying to us about it.

Before you proclaim “I never do that! How very dare you,” keep in mind that this pattern shows up all the time. Popular frameworks like Angular and Ember actually encourage this kind of thing through the controller pattern. This is a sneaky trap that is hard to avoid.

Although we can’t quickly resolve the code smell, let’s take a look at a remedy for the lie that is our “get” method name.

Now we understand and declare what the method does. For some people this is enough and we need to go no further. I, on the other hand, feel this is still rather suspect and would prefer to see a cleaner, more elegant construction.

Separate The Activity

The issue I draw with our updated object is, we have one method which does all the things. This is a really bad idea since it really doesn’t protect the programmer from a micro-god function. (Hey, You can have micro-frameworks and micro-services.) Effectively we have fixed the naming problem, but we haven’t actually resolved the smelly code which lives within our method.

Typically I prefer a single function which will return the current state of affairs and other function, if you MUST, which modifies the internal state. This kind of separation of concerns actually helps to keep object state sane and useful. If not for the exposed internal value of the object, we would be on our way to saner code.

We can see this code actually separates the functionality and has the lovely side effect of making the code more readable. If I were working in a project using an MVC paradigm, I would call this good and move on. We have separated the behaviors and tried to keep everything clean, tidy and meaningful. Our view would be able to access the values it needs and we keep our state management safe from accidental update.

Turn Up The Encapsulation

From here we can start looking at working on our fine detail. Up to now, we have accepted that our internal values are exposed and available for the world to manipulate, AKA Indecent Exposure. It’s time to fix that little bit of nastiness and make our object water- and tamper-proof.

The only way to actually protect a variable from external access in Javascript is through closures. Since functions are objects and objects are built atop function constructors, we can perform a little scope management surgery and make our object really safe and secure. Let’s take a look and see what we can do to lock things down.

This code does a little fiddling around with scope by partially applying the object’s internal state to our get and set functions. This protects our variable from being accessed by the outside world, but allows our get and update methods to access our value freely. When your data must be locked away, this will get you there.

Our Code Goes to 11

In order to finish up this journey, it seemed only right to create a completely pure, immutable object just to see where it would lead us. If we were to really go all the way, we would need to do a little more work to ensure everything still worked as we would expect.

We know the variable “value” maintains a count for some reason, so it will be important to ensure value is always an integer. We also want to make sure the get method always gives the current count. Finally, update should do just that: update the count value. What does it mean to make an update if everything is immutable? Let’s have a look and find out.

This is just chock full pure functions and added behavior. With all of that added behavior, we get something magical. Instead of having an object which is mutable and, ultimately, somewhat unpredictable and hard to test, we end up with an object which has the following properties:

  • Immutable
  • Contains pure methods
  • Has a single, pure, static method
  • Is compositionally built
  • Updates through new object construction

This whole object construction could lead us down many discussions which would get into types, values, mutability, function composition and more. For now, it will suffice to say, this kind of development creates the ideal situation for developing safely and really turns our code up to 11.

The numbers all go to 11.

Summing Up

Although we got a little spacey at the end, the important thing to take away from this whole thing is, any time an object is built and modifies its own state through method calls, the methods are actually relying on shared, mutable state.

Shared mutable state in an object really is just a micro-global and should be viewed as such. This means, any value which can be accessed and modified should be considered unsafe and untrustworthy. Untrustworthy data should never be viewed as the source of truth.

From here forward, if you start to add a variable to an object or module, ask yourself, does this really need to be global, or can I localize it? Perhaps you will find a better way to keep your code clean and easy to reason about.

Comments Off on Objects Are Still Shared State

Pattern Matching in Javascript

For more than a year I have been considering the idea of pattern matching in Javascript. I know I am not the only one trying to solve this problem because there are a handful of resources where people have put together propositions for solutions, including a Sweet.js macro called Sparkler, and Bram Stein’s blog post and associated Github repo.

Although I really, really like the idea of a macro to handle pattern matching, I fear people will throw it out immediately since pattern matching by itself is already an, sadly, obscure topic. This means anything that requires a macro package will probably turn the general populace off, especially since I haven’t met anyone in my area who has heard of Sweet.js except me.

Although I like Bram’s approach to handling macros with a function library, it looks like he didn’t get a chance to make much headway. That’s really unfortunate since I think he was headed in a good, although kind of simple direction.

Before we go any further, it is important to discuss the idea of pattern matching for the uninitiated. Pattern matching is a functional means to quickly look at the shape and signature of data and make a programmatic decision based on what is there. In other words, pattern matching is like conditionals which have spent the last 10 years at the gym.

Imagine, if you will, conditional statements which looked like this:

Even this isn’t really powerful enough to truly capture what pattern matching does, but I think it gives a little insight. Nonetheless, if we had a construct which would give us the ability to match on an entire set of conditions within our data structures, the face of Javascript programming would be a very different place.

Pattern matching is not just about reducing keystrokes, but it actually redefines what it means to actually describe and interact with your data altogether. It would do for data structures what regular expressions have done for string manipulation.

Pattern matching is the dream.

So, after doing a lot of thinking, I think I have settled on a means to give this dream the breath of life. Unfortunately, I believe it is unlikely that the path to data Nirvana will be easy. I have a suspicion, this is the same issue Bram encountered. Looking at the ~1400 lines of code that make up the Sparkler macro, pattern matching could be a tricky problem.

Function and Contract

I looked at the Sweet.js macro, Bram Stein’s early exploration and the match behavior in both Scala and Racket. I decided I needed something which felt like fluent Javascript instead of succumbing to the Racket nut which lives inside me, so I opted to avoid the hardcore Lisp syntax. Scala had a closer feel to what I wanted so I kept that in mind. Bram’s example felt close, but a little too muddy and the Sweet.js macro just felt a little too much like operators instead of functions. What I landed on was this, () => () => any; that is to say a function ($match) which returns a function (pattern assembly) which returns the final result of the pattern matching. Here’s an example of a simple exploration, drawing against Bram’s factorial implementation.

It’s easy to see the first call is just $match(n). This returns another function which takes a function as an argument; i.e. $match is a higher-order function which returns a higher order function, which takes a function as an argument, which then does stuff and returns a result. Another way of looking at this is $match is a function which chains to a function which is designed to perform pattern assembly. Once the pattern is assembled, everything is executed and we get a result.

Clear as mud?

Expanding the Concept

This small example seems pretty simple. Check for equality and if nothing works, then use the else clause. This is a little condition-block feeling, but I think people will understand the else clause better than anything else I might have put in there.

Anyway, digging in a little further, I wanted to also be able to quickly and easily match arrays, objects or other things as well. This simple equality checking was not enough, so I started expanding, moving into some sort of factory behavior to create matchers on the fly. This brought me to an example which was a little more interesting and a lot more complex.

Here I am returning a string based on the pattern of a pair (2-valued array) array being treated like a vector. If the first three patterns match, we get a string describing the axes the vector lives on. If the vector is not a pair, or it contains something other than numbers, I want to return a type error with a message explaining the provided vector was invalid.

This bit of logic is significantly more complex than our previous factorial example and leaves us in a place where the code is descriptive, but perhaps not as readable as we would like. Moreover, I thought about what I really want to be able to say and it made more sense to, perhaps, create something of a pattern matching DSL. (domain specific language)

Matching on a DSL

If I was going to invent any kind of simple language for expressing matching behaviors, I wanted it to be less cryptic than regular expressions, but I also wanted it to be terse enough that it didn’t become some giant, sprawling string someone would have to mentally parse to really understand what was happening. What I landed on was a simple near-Javascript expression of what the values should look like when they properly match our criteria. This turns our earlier expression into the following.

I reduced the type descriptor for brevity, opting for an angle-bracketed character. Now we can wrap up our expression in a single pattern call and get something the matcher can quickly and easily execute to verify whether the vector matches our requirements or not. This, however, also means I am responsible for generating an AST (abstract syntax tree) for these expressions. Of course, if I am going to do that, it would be best to create one by hand so I can see what I am actually contending with.

Matcher Abstract Syntax Tree

The AST for my matcher language would, ultimately, link in with an underlying state machine of some sort, but I won’t dig that deep right now. Nonetheless, what I ended up with, when constructing an AST is long, but relatively declarative. This means, I could, theoretically, start the entire process NOT at the language level, but instead at a place which people would more readily understand. Let’s have a look at the AST replacement for our matching behavior.

It’s long, and probably overkill for the problem presented here, but it gives us a real view into the guts of the problem and a way out of the mud. This is, also, unfortunately all I could pull together in time for this post, but I feel like we covered a tremendous amount of ground. I will continue to experiment with pattern matching and, perhaps, by next time we could even have a working object model to build our tree with. Until the next post, keep coding!

Comments Off on Pattern Matching in Javascript

Math for Programmers: Difference of Sets

Last post we discussed union and intersection of sets. These two functions are common and well used, so they are quite important to understand at a deep level, especially if you work with databases on the regular. It can also be helpful to understand these behaviors if you have lots of sets of simple data which need to be combined in a straightforward way.

Difference Explanation

One last, critical, function which is typically used on two or more sets is the difference operation. The difference of sets can be characterized as A – B where the outcome is the set A with all elements shared with set B removed. We can visualize the difference of sets with the following diagram.

Venn diagram of a difference of sets

Unlike union and intersection which are commutative, the difference of two sets is not. This means that A ⋂ B and B ⋂ A are the same operation; the same can be said for A ⋃ B and B ⋃ A. The difference A – B is not the same as B – A. We can create a concrete example as follows.

Clearly these two differences are distinct and different. It is quite helpful to understand the order result of set difference when trying to apply functionality to it. we can create a function, called difference, and apply it to two sets. The action would behave like the following diagram:

Visualization of a difference function

In order to apply our difference function, we need to use a couple of helper functions we introduced in the last post: unique and buildSetMap. These will be important for isolating unique elements and eliminating or keeping them according to our difference functionality.

Predicates as Sets

We can describe a set by way of a predicate function. Effectively, anything which matches the condition of the predicate can be viewed as part of the set while anything which does not match the predicate is not included. A good example of this kind of set partitioning would be the set of even numbers. We could pick values with a function called isEven, which would give us a set like this: {2, 4, 6, 8, …}.

We can describe a more general purpose predicate which simply tests if a value is contained in a set built by our buildSetMap function. The behavior would be simple: test that any value which is provided exists in our set and does not resolve to undefined. Let’s have a look.

We can, now, easily test if a value is contained in a set. This simplifies our problem significantly. Now all we really care about to take a difference is whether a given value is not contained in our set; i.e. then it is part of the difference.

Javascript has a function, filter, which is very closely related to both the intersection and difference of sets. If we choose a predicate which includes all values contained in a set, filter will return the intersection of the set of all values which match our predicate value and the set of values we are testing. If, on the other hand, we use a predicate which only keeps values which are NOT in the set, we get the difference instead.

We can use the factory pattern to keep our code clean and readable, while building a useful difference predicate function. Let’s have a look at the code that makes this work.

Implementing Difference Function

Now we are ready to take the difference of two sets. We have a difference predicate factory, a unique function and a buildSetMap function. Bringing filter into the mix means the code almost writes itself. Let’s build our difference algorithm.

This difference function will produce the difference of any two lists of primitive values. This means our original example of A – B can be done with a small, easy to read line of code; difference(A, B);.

Symmetric Difference Explanation

There is another difference operation which has a special name in computer science, the symmetric difference. Mathematically a symmetric difference can be written one of two ways, (A – B) ⋃ (B – A) or (A ⋃ B) – (A ⋂ B). Both of these operations resolve the same way, which can be visualized by the following diagram.

Venn diagram of a symmetric difference of sets

To make this more clear, let’s have a look at a concrete example of a symmetric difference using our original sets A and B.

What all of this really means is the symmetric difference takes everything from sets A and B and excludes the elements they share. A common example is a graph of students taking Math and English but none of the students which are taking both. We can create a function symmetricDifference which performs this operation and lives between the definition of sets A and B and the resulting set.

Visualization of a symmetric difference function

Symmetric Difference Implementation

To create our implementation, I opted for the difference of the union and intersection of A and B. This means we will first compute the union and intersections of our two sets and then take the difference of the two resulting sets.

Once again we see the code practically writes itself. Since we already have functions to perform each of these operations on their own, all we have to do is simply chain them together in a meaningful way and our output simply emerges with nearly no effort at all.

Summary

This closes up the introduction of basic sets and operations including algorithms for acting on lists as sets of data. We discussed how lists and maps relate to sets, what a union and intersection are as well as how to write linear implementation of union and intersection algorithms. We addressed how sets can be defined conceptually with predicate functions and how they interact with concrete sets of data in our programs. Finally, we looked at the difference and symmetric difference operations as well as functions which perform our difference functions in linear time. With all of this closed up, we are ready to start performing more complex manipulations of data using higher order functions which we will discuss in upcoming posts. Until then, keep your code clean and use sets to make your programs better!

Comments Off on Math for Programmers: Difference of Sets

Speeding Up Your App with Request Caching

Recently in my Mainstay Monday posts I’ve talked about creating linked lists and queues in Javascript. Each of those topics is so dense that just writing about the basics of creating and using them took full blog posts. Really all of that was the lead up to today’s post.

I’ve worked in a couple of different, large single page applications and in every one I have, ultimately, encountered a need to cache requested data and respond to multiple functions needing that data before the original request is complete. No promise framework or other specialized library ever fit the need because, really, the call should only ever be made once.

I’ve had team members solve this problem in a naive way and simply make the call over and over again. What happens, though, if the data you’re requesting is large and takes a long time to retrieve? This means you have now introduced multiple seconds of latency into your app. I think we can all agree that waiting for 5-20 seconds for data to come back is about the worst thing you can do to a user. They get frustrated and confused. They think the app has stalled or their browser has crashed.

Problem #1: I need to store the data when I get it.

This is easy. If you just need to store the data and retrieve it upon request, you can create a hashmap with keys and values. Now, when a request comes in, first your data service will look in the hashmap and see if the data already exists. If not, you go fetch it, bring it back and then, upon return, you hand the data back into your app.

This is the most basic kind of cache and it will suffice for calls that are made infrequently. Initial data for your app to bootstrap can be handled this way. Typically a single request will be made and you can just go fetch it, then cache it. If the app wants to rebootstrap for some reason, the data is in memory and you can skip the wire call.

The more challenging issue is this: what if you have data that is requested often?

Problem #2: I need cached data to only be requested once, but the program asks for it everywhere.

This is where it gets really interesting. It’s quite common for a program to need to refer back to permissions and user capabilities often. ACL tables can get quite large and it is preferable to only request these once. The problem is, the program will need access, possibly multiple times, for even a single page. This means your application will request the same data multiple times before the service you’re accessing can return.

I’ve seen a page make 100+ requests at the same time to get data from a service. It’s not pretty.

Fortunately, queues provide the solution for this. We can queue all of the callbacks that our application generates and resolve them at once when we get the data back. This means we could, in theory, request the data on app bootstrap and never request it again. Worst case scenario is we request it just in time and the user has to wait once.

This is where the real meat of the problem is. We need to construct a queue backed request system with a cache layer to manage our data. This all sounds a bit scary but, once we break it down, it’s all just bite-sized pieces we can easily manage. We have even already decided on the data cache structure.

Before we start down this road, I would like to point out, a friend of mine introduced me to a rule I use all the time. It makes testing easier and it makes coding easier.

Never create and use an object in the same place.

The easiest way to answer this rule, for our current problem is with the factory pattern. Our factories are going to be relatively uninteresting, but because it creates good seams to work with in our code, and it does a nice job of separating our concerns so we can reasonable, correct abstractions.

So, since we know our mechanism is going to be queue-backed, we need a linked list. I went ahead and created a linked list item factory as a gist. It creates generic linked list items, so you could really use it for anything. We’re going to use it to construct our queue. Here’s our first factory, linked list items:

Once we have our linked list item factory set to go, we are ready to construct our queue. Once again, we are going to want to work with a factory. Our queue logic comes straight out of the queues post, it’s just wrapped up in a factory so we can easily separate it and work with it alone. Here’s our queue:

Now is where we start breaking new ground. Our cache, and its factory, are going to handle a few things. Consider this a little like learning to juggle. We have to get things in the right order, and it’s all interconnected, so you might want to read the code a couple times. Let’s have a look at the cache factory and then we can talk about it.

The short and sweet version of this is, we receive a local request for data, if it is in the cache, we resolve the request and move on. If we don’t have the data, we queue the callback with any other outstanding callbacks and wait for our service to return the data we need. In order to ensure we don’t have overlapping concerns, we rely on a cache instance per unique data request. Basically, this means if you make a request with { id: 1 }, it should always go through the { id: 1 } cache. This way if your application needs to come back later and request data using a different id, it can without colliding with the original data cache.

To expand this idea, let’s take a look at the steps that happen.

First, we have a cache factory. The factory takes in a request function, which it assumes only needs a callback to be complete. With this function, it news up an instance of the cache object. By using a factory, we can guarantee instantiation correctly, every time. Here’s what it would look like in code:

I’m assuming permissionService is already created and get is a method to perform a standard HTTP GET. Honestly, this could be anything, just as long as all of the correct parameters are bound.

It’s important to note that no request has been made yet. All we have done is create a cache we can make requests against. Our app is still sitting there patiently awaiting instructions for what to do. This entire setup process takes microseconds to complete and you now have everything you need to manage bursts of traffic gracefully.

Once we have our cache ready to go, we can make a whole bunch of calls and it will only make a single call across the wire. This gives us a major performance boost, which allowing our app to carry on blissfully unaware that anything has changed. Here’s what it looks like:

The first request, regardless of which it is, will cause our service to create the cache. Each subsequent call will just end up the queue. Once the request comes back from our remote service, all callbacks will be resolved in the order they were received. Even better, if something else is kicked off in the meanwhile, this will simply be added to the queue and all is set and ready to go.

Adding this kind of data management to an application adds some complexity, so it may not be worthwhile to manage all data requests this way, however, when a particular behavior starts making lots of requests across the wire, this is a great way to throttle the requests back and improve efficiency in your app. The best part, as long as you are working modularly, is that you will only need to introduce changes in one place. This means the bulk of your application will remain precisely the way it is today while repairing a bottleneck that can slow your app down and frustrate users. So, get to profiling your apps and cache some data.

Comments Off on Speeding Up Your App with Request Caching

Mainstay Monday: Queues

A couple weeks ago, we looked into linked lists. Sadly linked lists are kind of a standalone topic that don’t use much more than basic objects in order to function as designed. Queues, on the other hand can easily spring forward from linked lists, and they are a way of working with data as you might with generators!

Queues are a great resource for dealing with anything from data stores which are being updated in one place and read from another to dealing with data requests against an endpoint and a cache. Queues give you a reliable way to store data and interact with it later in the same order. Since functions are first class in Javascript, this means functions are actually data, which can be stored in a queue as well. This kind of power opens a world of possibilities.

Let’s take a look at a queue in action.

That’s a lot of code for a simple example, but I think you’ll get the idea. Essentially we want to call a service and get a value, resolve the value and store it in the queue. One that is complete, we want to log everything that was queued up. The problem we would have run into is, the queue may not be filled completely before we start dequeueing. This allows us start with the first value and let the rest filter in over time.

Queues are a common data structure which are used throughout programs in every language to solve the same kinds of problem: we want to perform one action and allow other actions or data to wait until we are ready. It’s a lot like people waiting to get into a movie on opening night.

Since I already talked about linked lists, you probably have an idea where I am going with all of this. Let’s use the list object we created in the last post to build our queue. It turns out that once we have a linked list item definition, we can create a queue with just a bit of effort.

There is a little bit of logic here to ensure we don’t leave dangling pointers and we don’t have null pointer exceptions, but other than this, we’re basically moving through a list that has the capability to grow on one side and shrink on the other. This is the perfect structure for dealing with data which isn’t infinite, but could grow to an arbitrary size at an arbitrary rate.

Why not just use an array for this?

It turns out we can do this in a quick and dirty way with an array. I’ve done it and you can do it too. I’ll even give an example of how to do it, but I would argue that you shouldn’t. Arrays are really, really good at handling random reads from a location. This means, if you have data you want to bounce around in, arrays are a good way to manage that. While you get this random access behavior, you have to pay for it somewhere. That cost is built in to the allocation and management of array memory.

Let’s take a look at a queue built on an array and then we can talk about the problems.

As you can see, this code is really short and easy to write. For a small queue written in a naive way, this will suffice, but there is something dangerous lurking just beneath the surface. When we create our array, it allocates space for the array to live in. This space will grow with our array at a linear rate, which is okay, though non-optimal. The real problem comes in when we perform a shift.

Shifting an array involves retrieving the value from the head of the array, and then moving each of the elements into a new position in the array to fill the head space which was shifted out of the array. This kind of element movement and array space reallocation is really, really slow.

This slowness comes from the fact that an array in Javascript has to abide by particular rules to be predictable. If we were to do the following and the elements weren’t moved as described here’s what would happen:

This kind of reallocation is exactly what we avoid by using a linked list. Linked lists grow and shrink in constant time and position 0 is always the head of the list. Since queues only ever interact with the first and last elements of a set of values, lists give us the improved performance we need to ensure, even with large queues, we don’t encounter the kinds of difficult to diagnose bottlenecks in our code that can cause slowness.

Queues are a great example of a use for linked lists in the wild and they provide a useful mechanism for lining up data and handling it in a predictable order. With a little creativity, queues can provide a means to manage a cache, handle processes in an orderly way and even provide the backbone for generator-like behavior. Take our queue code and play with it. You might find a solution to a problem that has been challenging you.

Comments Off on Mainstay Monday: Queues