Monday, December 8, 2014

Design Patterns: Builder

Prerequisites: It helps to be familiar with design patterns, in general, and UML class diagrams.

Builder is a design pattern concerned with object creation. If you're already familiar with lists in Python or arrays in Java, you're aware that they provide you with the ability to append and remove or pop elements. Because these data structures must anticipate mutations, they often come with extra allocations in memory to handle the size increase. This comes at a cost. Builder provides one solution to this problem, which we'll hear about later. For now, let's review a UML representation of this pattern:

Image source: Wikimedia Commons

In this diagram, you can see that ConcreteBuilder inherits from Builder and Director has an instance of, or aggregates, our Builder. Director is the caller in this scenario and is free to call buildPart() as many times as needed, until it's ready to finally getResult().

Purpose

As we've seen in the diagram, Builders are designed to instantiate the object and provide the ability to assemble all of its components, and then return the constructed, fixed object at once. Builders also give the function caller control in putting this object together, often providing an API of methods like append or insert. The Java StringBuilder class is the perfect example of this.

// java
// creates empty builder, capacity 16
StringBuilder sb = new StringBuilder();
// adds 9 character string at beginning
sb.append("Greetings");
sb.append(", fellow travelers!");
sb.toString() // "Greetings, fellow travelers!"

So why is this useful? Well, it's a great way to build a complex object before calling that object's constructor. This type of approach also comes in handy when dealing with lists. Appending to lists is actually very expensive. Appending to strings is even more expensive because strings are immutable. Every time you append to a string, you're recreating the object, allocating more space and sequentially moving those elements along. With a StringBuilder, you just keep appending to the object, and receive your string at the very end, eliminating the need to move memory locations.

JavaScript: The Definitive Guide says the following about strings in JavaScript: "In JavaScript, strings are immutable objects, which means that the characters within them may not be changed and that any operations on strings actually create new strings. Strings are assigned by reference, not by value. In general, when an object is assigned by reference, a change made to the object through one reference will be visible through all other references to the object. Because strings cannot be changed, however, you can have multiple references to a string object and not worry that the string value will change without your knowing it".

Should I Use a StringBuilder in JavaScript?

In most modern browsers, the short answer is no. A custom StringBuilder doesn't yield a significant return over string concatenation in JavaScript. What about using array.join() over string concatenation? Find out for yourself by running these jsperf tests. Browsers often account for common programming practices, good or bad, in order to optimize client-side performance. One example is no longer needing to cache the length of an array prior to iterating through it with a for loop. See benchmarks here. Take a look at the following code to see how string concatenation has been optimized, internally:

// ECMA-262, section 15.5.4.6
function StringConcat() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined", ["String.prototype.concat"]);
  }
  var len = %_ArgumentsLength();
  var this_as_string = TO_STRING_INLINE(this);
  if (len === 1) {
    return this_as_string + %_Arguments(0);
  }
  var parts = new InternalArray(len + 1);
  parts[0] = this_as_string;
  for (var i = 0; i < len; i++) {
    var part = %_Arguments(i);
    parts[i + 1] = TO_STRING_INLINE(part);
  }
  return %StringBuilderConcat(parts, len + 1, "");
}

Conclusion

If this is your first exposure to design patterns, I hope this has been enlightening. Please continue to read up on them. And don't just stop there. Always be on the look out for all the creative solutions that come out of the open source community, or even the bodies behind languages, themselves.

Python is a great example of a language that's made tons of optimizations over the years. Have you ever heard of double ended queues? Python's collections.deque are more elegant and much faster than Python lists. Where adding or popping items from either end of a queue has O(1) complexity, inserting and removing items from the front of the list is O(n). If you're not sure what that means, read up on Big O Notation or check back for an article, soon.

No comments:

Post a Comment