Web Sockets: Random Number Streaming

I have recently been playing with web sockets because I wanted to get a better understanding of how to use them. A web socket is a full duplex TCP connection between web browsers and web servers. This is not to be confused with earlier techniques with similar aims like long-polling and Comet. Web sockets actually have their own RFC. They are a standard. All the major browsers have implemented it. This means web sockets are not tied to any particular language or server. Below I will show using web sockets in plain JavaScript, Node.js, and Java.

Node.js Server

Here is a Node.js server that sends a random number to everyone connected to it, every second, on the same channel. Obviously this is not that useful, but it could represent a stock price for example. I found the ws module to be easy to use for the web socket server implementation. Another module socket.io seems to be more popular but you need to use it in the client as well. For this learning exercise I wanted to use native web sockets in my client.


Java Server

Here is the same random number sender implemented in Java. I ran this on the recently released WebSphere Liberty Profile 8.5.5.2 which added a web socket feature (full disclosure I work closely with this product at IBM).


JavaScript Client

My client can talk to both servers. I probably went overboard, but I used the same MVC-style from my Client-side MVC with JavaScript blog. The important part is lines 9 through 12.


A screenshot of the client receiving random numbers from the Node.js server:

Memoization: Fibonacci Sequence

Memoization is an optimization technique that caches computationally expensive function calls. I first learned of it in Stanford's Algorithms class on Coursera.¹ It is more common in functional programming than object oriented programming because the function being cached can not have any side-effects, and that is, of course, often the case in functional programming. It is also commonly used by lazy data structures. The downside of memoization is that more memory will be used, but for some functions, as you will see below, it is well worth it.

A function that returns the nth Fibonacci number is the quintessential recursive function. I still remember that was the example used when I first learned of recursion. It is actually often implemented inefficiently, though, the standard recursive implementation being O(fib(n)) = 2ⁿ.

Python

Python makes memoization easy because you can decorate any function with a memoization function.

Scala

Scala does not make it that simple. Hopefully it will be built into the language in the future. This naive implementation only caches the original function call. The recursive calls do not know to use the memoized wrapper.


This blog correctly points out this problem with memoizing a recursive function and has a great technical explanation of the solution. In summary, you have to use something called a Y combinator to correctly implement the memoized wrapper function in Scala. It is basically a high-order function that returns a recursive version of a non-recursive function. I will defer to these other resources for a proper definition.


Notes

In Scala, for example, I could get up to n=45 in about 20 seconds with the standard un-memoized Fibonacci implementation. With the correctly memoized version I can run n=1000 in under 1 second because the memoized recursive implementation is O(fib(n)) = n.

The recursive Fibonacci implementation is not tail-recursive (which I covered in a previous blog), so you pretty quickly will hit a stack overflow error. In my Python implementation I even had to explicitly set the recursion limit higher than the default.

Also note the use of currying (which I also covered in a previous blog) in the nonRecursiveFibonacci Scala function.


1 I would highly recommend this class. It is better than the algorithms class I paid for to get my CS degree.

Fixing My Asynchronous Non-blocking I/O Callback Hell With Monads

In my previous post Asynchronous Non-blocking I/O Java Echo Server, I looked at non-blocking I/O from the Java perspective. My echo server used the callback functionality known as a CompletionHandler in Java 7, but it left something to be desired. Mainly I had a callback inside a callback inside a callback. Well, now Java 8 is released and I set out to fix it inspired by Monadic futures in Java 8: How to organize your data and avoid callback hell.

Monads surround computations and can take actions on them. They help chain computations together because they take in an action and then return a new monad surrounding the computations that had the action executed on them.

I am still trying to fully understand monads myself, so I am not going to act like I already do and give detailed information here. I think it's easier to understand from examples, anyway, instead of reading about category theory. The above definition will make more sense after looking at my new server code and seeing the chaining in action.

My New Server Code

A promise is a type of monad common around asynchronous operations. I used the new monadic CompletableFuture class to wrap my asynchronous computations.

My Thoughts

1. I like this better than my Java 7 version in terms of readability, but it would still be a lot cleaner without checked exceptions like in Scala.
2. This is not really non-blocking. Even though it is done asynchronously, I block waiting for a Future to complete three times. There is not a good relationship between Future and CompletableFuture to help avoid this as far as I can tell.
3. This Java 8 version is slower than the Java 7 version. My theory is that, even though the blocking calls are handled asynchronously by the CompletableFuture class, explicitly blocking the thread with the get() instead of letting Java handle it with a callback is what makes the difference.

There is not much Java 8 code out there to look at, so what would make this better? Can I get rid of the blocking get() calls somehow? Why is it slower than the Java 7 version?

Notes

A future represents a result that does not yet exist (and might not ever exist). Futures are read-only. A promise is the container that completes a future. Promises are writable.

UPDATE:

I posted a Scala version of this at Scala Asynchronous IO Echo Server.