Type erasure misconceptions in Java

Generics were added very late in Java (J2SE 5) and one of the challenges with it was to maintain backward compatibility. Type erasure is a technique that the language and runtime designers chose to overcome this problem. Here is a simple demonstration of type erasure in action.

import java.util.ArrayList;
import java.util.List;
 
public class Erasure {
    public static void main(String args[]) {
        List<String> ls = new ArrayList<String>();
        System.out.println(ls.getClass().getName());
 
        List l = new ArrayList<String>();
        System.out.println(l.getClass().getName());
 
        Object o = new ArrayList<String>();
        System.out.println(o.getClass().getName());
    }
}

The output is as follows

java.util.ArrayList
java.util.ArrayList
java.util.ArrayList

Querying an object instance does not reveal the generic types associated with the instance.

The not so obvious aspect of type erasures is that the erasures happen on object instances but do not happen on type declarations. Here is a sample code that shows the effect

import java.lang.reflect.Field;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.List;
import java.util.Map;
import java.util.Set;
import static java.lang.System.out;
 
class PokeMe{
	Map<Set<Integer>, List<List<String>>> l;
}
 
public class GT {
	public static void main(String args[]) throws Exception {
		Class<PokeMe> clazz = PokeMe.class;
		Field el = clazz.getDeclaredField("l");
		Type t = el.getGenericType();
        typeSniffer(t);
	}
 
    private static void typeSniffer(Type t) {
        typeSniffer(0, t);
    }
 
    private static void typeSniffer(int level, Type t) {
        final StringBuilder padding = new StringBuilder();
        for(int i = 0; i < level; i++) {
            padding.append('\t');
        }
 
        out.println(padding.toString() + t);
        if(t instanceof ParameterizedType) {
            ParameterizedType pt = (ParameterizedType) t;
            for(Type at: pt.getActualTypeArguments()) {
                typeSniffer(level + 1, at);
            }
        }
    }
}

Running this code produces the following result:

java.util.Map<java.util.Set<java.lang.Integer>, java.util.List<java.util.List<java.lang.String>>>
	java.util.Set<java.lang.Integer>
		class java.lang.Integer
	java.util.List<java.util.List<java.lang.String>>
		java.util.List<java.lang.String>
			class java.lang.String

This often comes as a surprise even to those who have been programming in Java for many years. The reason why this is different from the earlier example is that we are inspecting declarations of a class member. Contrary to popular opinion, type erasure does not occur in the case of any sort of declaration. This is true for the following:

  • members of a class
  • argument types of methods
  • class definition themselves (when they inherit from a base type has generics and the class in question constrains those values)

Having this ability gives great validation power to developers who build reflection based frameworks in general

Posted in Uncategorized | Tagged , | 1 Comment

IDE provided illusions for Java

Lambda functions, or more specifically the lack of it has always been an annoyance in Java. The closest alternative has been implementation of interfaces as an anonymous class. Here is an example:

unfolded anonymous class

IntelliJ does a nice folding of this code to give an illusion of closures. This makes reading of the code a little more fun as seen here:

closure illision

Posted in Uncategorized | Tagged | 1 Comment

“Server side” languages in 2012

Yes, 2013 just began but this post is about my views on programming languages that I have reasonable amounts of professional experience in. This post was inspired by what one of my former colleagues had to say on couple of days ago. Note that it is not meant to be a rebuttal, it just happens to be the tipping point that got me writing.

I come from a very varies lineage: first few years of C & C++, then lots of perl & php, followed by Java & python. Here is how I feel about those languages now.

Perl

Perl is a much better bash. The shell scripting utilities (which is not the just shell itself) never managed to operate seamlessly with say an ftp resource, a http resource etc. etc. and also never managed to have tools to work with json, xml, yaml etc. etc. So if I had to write a for loop to fetch a bunch of urls, parse the json, then do a “grep” on it, I’d be coding in perl. An occasional easy access to the DB doesn’t hurt either.

However, the runtime isn’t fast enough and the general maintainability of large programs does turn out to be more complex than necessary. One of the emotional reasons that I gave up on the language was my loss of faith in the community given how long they have been dragging their feet as far as making perl 6 available.

PHP

PHP as a full blown programming language is plain horrible. What was originally meant to be a templating language alone got so may things glued via duct tape on it that it is very hard to find an underlying philosophy besides “someone added a feature in isolation overnight and never looked back”.

Python

Python really has turned out to be by favourite general purpose scripting language. It seems to have very few surprises (try figuring out what expressions evaluate to false in perl and you shall be shocked) by having some minimal restrictions in place like dynamic + strong typing. Not having to worry about integer overflows, having access to generator functions etc. etc. makes it modern enough for me. The maintainability side of things also looks reasonable given that code organization aids in retaining sanity, the “import as” directives provides nice ways to swap in different implementations without having to go through the rituals of programming to an interface.

The scary part of python however is that it is the most insecure language I’ve seen to date. Entire functions or even libraries can be monkey patched. What this means that someone could have replace the function that writes to a local file with a function that wipes off your hard disk and you can’t prevent it. And then there is the fact that there are no constants, you are supposed to be a good child and not try and update a constant.

C

This language was brilliant and awesome for almost 3 decades but it just doesn’t belong to this age. It is an extremely fragile language to program with. Contrary to popular opinion, the lack of automatic garbage collection is not what I consider as the source of fragility. Anyone who spent their time understanding the true language standards and also the contracts of the standard libraries knows that undefined behaviour is the norm and not an exception.

One source of fragility is around function signatures. The language was designed in the days where programmers always followed the gentleman’s code of honour and never changed the signature once it was published. Not honouring this code results in silent memory corruption that reflects neither immediately when it happens nor even in the same code locality where it occurs. A lot of folks might write this problem off as “fire the programmer” but it is not simple when you are relying on an intricate chain of say fifty different libraries. A modern gvim has more dependencies than that.

A more credible and painful version of the problem is around managing definition of structs. Re-ordering of fields is surely asking for trouble. Adding a new field is also asking for trouble. These two operations unlike deleting a field or redeclaring a type are semantically safe as far as existing code is concerned. However, doing either of these safe operations actually requires you to recompile almost every piece of code that uses the struct as the memory layout has changed.

A translation unit of compilation in almost all languages, C included (pun intended) is at a file level and not an application level. A general classification of the problems is that way too much assumptions and commitments are made in the compilation phase  that really should be deferred to either the linking phase or the loading phase.

The lack of easy access to stack traces in case of non-fatal errors (usually accomplished by exception propagation + catching & logging at higher levels) another non-modern aspect of the language. Again, this decision was fine decades ago when there was no expectation of using multiple vendors’ libraries in your code and being open about it and saying hey, I used someone else’s code and that code has issues, so go bug them. Open source didn’t exist in 1970s and so it was fine back in the day.

People love C as it does exactly what you ask it to and you can ask it to do quite a lot of esoteric things. While all of that is great, it has rightfully fallen out of vogue as it always requires to say what needs to be done in excruciating levels of detail. All said & done, it still remains the language of choice if you are concerned about memory layout and want to have great control over it.

C++

Contrary to popular opinion, writing decent C++ on large projects is actually much harder than writing C programs. A good example of what it takes to do so can be found by looking at Google’s C++ style guide. People have often criticized it for being too restrictive but this level of clamp down is actually needed to remain sane for large code bases. If you think this is a one off situation, have a look at what the KDE guidelines look like. Their bread & butter is the d-ptr (a.k.a. p-impl idiom) which is clever but painful.

The compiler implementation story was outright shoddy for a decade wherein each vendor had a very different way of doing things and even different versions from the same vendor had very different language level support. The amount of #ifdef magic needed for a reasonable portable source code was horrendous. Enough people made a living just to get the code to compile faster or compile on more than one platform/vendor.

It was a good learning language just like C in that it helped one understand the underlying implementations an OO language but I believe its utility now is largely historical.

Java

Java is one of those languages that I’d despised for the larger part of previous decade (2000-2009) but I am now a lot more open to. People confuse Java the programming language, JVM the runtime, J2EE as defined by Sun & popular Java based frameworks & libraries. I am going to stick solely to Java the programming language in this section.

As a languages, Java is probably the most well thought out & unambiguous language for complex environments. Here is are a list of things that it supports at a core language level and was the first mainstream language to do so in most cases

  • Ability to mix trusted & untrusted code in the same application and manage it via security permissions.
  • A credible sandbox implemented at the loader level that lets you have some code run in shared space and some in private space within the same process.
  • A metrics collection framework that lets you expose it from any running instance of the program
  • A portable way to extend the language. APT acts as a compiler extension code that is supposed to work with any compiler that supports JLS5 or above
  • Reflection that isn’t dog slow
  • Acknowledging concurrency needs from the very first day and having enough language constructs for it (though bulk of the nicer libraries didn’t become a standard until the release of J2SE 5)
  • Super clear definition of the memory model behaviour under concurrency
  • Standardized library artifacts that could be reliably decoded for further inspection
  • Acknowledging the need to have a persistable, byte-stream representation of objects.
  • Support for desktop application development as part of the core library (a big deal back in the day, not so much now)

Much like how I said, I don’t hate C for manual memory management, I actually don’t like Java for automatic garbage collection. At least, that doesn’t make it into my top 5 list. The language has the static type safety of C, the ability to expand your structs in a semantically safe way without a full recompile and the python like runtime safety of validating all cross file signature assumptions on first invocation.

The place where it gets a rap on the knuckles is that it is a highly idiomatic world to program in. A lot of these idioms feel like elaborate ceremonies whose sole purpose is to increase SLoC. These idioms have more of declarative feel as opposed to an imperative feel. This is the reason why even C programmers find it annoying although the real lines of code needed to get almost anything done in C is actually higher than it is in Java. The problem gets magnified by the plethora of poorly trained programmers and frameworks designed to cater to their needs whose belief is that the more ceremonious the code feels, the better is the quality of code.

My take is that if you have to support a vast project and you have a few level headed technical people at the top, then Java isn’t a terrible choice. But it is clearly no substitute for any of the p* languages in areas where they are known to shine.

Sidestep: The JVM

If you are running some sort of an interpreted language (anything besides, C & C++ in list above), then one must look at the characteristics of the interpreter in addition to the language to understand the performance traits of running a program that is written in a certain language. While I’d have to say a few things about the interpreters of all the p* languages, I’d just gloss over them by saying none of the default implementations are any good when it comes to performance. They completely miss the baseline that is C.

The JVM in recent years has matured to be scarily fast. While everyone knows the theoretical possibility of interpreters also acting as profilers that can recompile a parts of running programming based on the profile data, it has historically proved to be a very hard problem to solve as most naïve implementations have the problem of the profiling and recompilation costs exceeding the benefits. The JVM and the CLR runtimes seem to be the only two credible runtimes that have a reasonable handle on the JIT compiler.

Going back to the performance baseline that is C, the whole cycle of profiling and recompiling with profiler data is incredibly hard both from an effort perspective and also what it takes to get it right.

All said and done, the JVM imposes 2 taxes on the running program that still remain a cause for concern. Both of them are a side-effect of having to support automatic garbage collection.

  1. The actual cost of running a GC is non-trivial. Getting it run at the right intervals and then getting it to back-off after partial progress is still a matter trial & error even to those who are well versed in this art
  2. There is an additional level of memory indirection that happens way more than C (but is no more than any language with automatic GC) is unavoidable. The JVM again shines here by in-lining where possible through a technique known as escape analysis

A positive side effect of the GC is that memory compaction can be done much more effectively. jemalloc is still in its infancy relatively speaking.

The most unpleasant surprise however is that some of the idioms entrenched into the larger java programming community are actually antagonistic to the JVM.  Some level of education is needed to retrain them to ensure that they don’t disable the JIT.

In conclusion

Nothing new here. There is no one true programming language to rule them all. There is no clear way to answer of C or Java is faster. And everything else you know already. This post was merely meant to document how I feel about various languages and that is what you get here.

Posted in Uncategorized | Tagged , , , | 2 Comments

Type safety & SLoC

I believe that SLoC is inversely proportional to code maintenance costs. There are situations where bad code needs more lines of code than good code. The argument for reduced SLoC is trivial in this case. Interestingly, the same holds true in situations wherein good code needs more SLoC than bad code. The need for an increased SLoC to keep things nice & clean suggests that trying to “maintain” this requires vigilance over a larger code base.

It is very common to hear about the SLoC needed to achieve the same result in various programming languages. This is then used as a basis for arguments over superiority or inferiority of languages. Unfortunately, much of these conversations tend to resemble political smear campaigns where jingiosm takes precedence over rationale. So let us explore what happens in a few popular programming languages.  We shall use the following entity to explore the implications

Entity: Company

  • name (a string)
  • number of employees (a positive integer)
  • annual gross revenue in USD (a floating point number)

C++

Strong typing (default)

struct Company {
  string name;
  unsigned employeeCount;
  double revenue;
}

This is about as good as it gets. Note that one little constraint on the number of employees is not enforced as this still permits a zero value to be assigned to employeeCount.

Ultra loose typing (uncommon, almost never done)

map < string, shared_ptr < void* > > Company

This is almost never done in practice but this essentially lets you have an open ended struct. You can extend this at will without any recompilation or worries about binary compatibility. However, the big, sharp, bleeding edge that this ends up opening is that it is now upto the programmer to remember what type of value is associated with which key type and then use it consistently. Failure to do would result in memory corruption.

Java

Strong typing + Encapsulation (default, done the stupid way)

public class Company {
    private String name;
    private int employeeCount;
    private double revenue;
 
    public String getName() {
        return name;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    public int getEmployeeCount() {
        return employeeCount;
    }
 
    public void setEmployeeCount(int employeeCount) {
        this.employeeCount = employeeCount;
    }
 
    public double getRevenue() {
        return revenue;
    }
 
    public void setRevenue(double revenue) {
        this.revenue = revenue;
    }
 
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
 
        Company company = (Company) o;
 
        if (employeeCount != company.employeeCount) return false;
        if (Double.compare(company.revenue, revenue) != 0) return false;
        if (!name.equals(company.name)) return false;
 
        return true;
    }
 
    @Override
    public int hashCode() {
        int result;
        long temp;
        result = name.hashCode();
        result = 31 * result + employeeCount;
        temp = revenue != +0.0d ? Double.doubleToLongBits(revenue) : 0L;
        result = 31 * result + (int) (temp ^ (temp &gt;&gt;&gt; 32));
        return result;
    }
}

This has always been the poster whipping child of mindless increase in SLoC. The worst part is that the number of holes in this implementation is staggering. The employee count can be -ve in this implementation. Also, the name of company can be null (which is different from an empty string). More code can be written inside the setters to handle these but that is just an increase in SLoC.

All of this bloat is actually not enforced by the language. It is possible to match SLoC of the strongly typed example in C++ in Java too (albeit with the deficiencies pointed out earlier around poor constraints). The bloat is throw in by OOP zealots who like to encapsulate the fields of an entity behind the accessors. What they do not realize is that the language has powerful constructs that lets them have their cake and eat it too.

Strong typing + Encapsulation (default, done the smart way)

The following code is exactly equivalent from a compiler’s perspective as the above but is orders of magnitude smaller from a maintainer’s perspective.

import lombok.Data;
 
@Data
public class Company {
    private String name;
    private int employeeCount;
    private double revenue;
}

The only change is that we have used an additional annotation based source processing library lombok that tucks away the ugly repetitive code. The tragic part of course is that there is exceptionally poor awareness of the existence of such tools and that fact that it is not a part of the language implies enormous amounts of bloated code base exists.

The “C++ way” that was alluded to earlier involves declaring all the members as public and doing away with annotation for the accessors. We still would need to use another annotation (EqualsHashCode) from lombok to provide proper object equivalence tests.

Ultra loose typing (not so uncommon)

Map<String, Object> company;

The above construct is also possible which is very close what we saw in C++. The only difference is that sloppy usage errors result in exceptions being raised as opposed to silent memory corruptions. This concept is widespread in the Java ecosystem and goes by the name of context maps.

Scala

Strong typing + encapsulation

Touted as the next java, scala has the lombok equivalent built into the language. Here is what the scala code would look like

class Company {
  var name : String
  var employeeCount : Int
  var revenue : Double
}

There are accessors getting generated behind the scenes that permit manipulation of these values. Much like using lombok with java, it is possible to selectively override these accessors.

JSON

Ultra loose typing (The only way)

Though not a proper programming language by itself, the format is so widely used that it deserves a special mention. Here is how the modelling would happen in JSON

 {}

This is as flexible and as uninformative as it gets.

ECMAScript/Javascript

Ultra loose typing

This is exactly what you saw in the case of JSON

 {}

Weak typing, no encapsulation

It is possible to have a rather well defined struct in the language. Here is an example

function Employee() {
  this.name = '';
  this.employeeCount = 0;
  this.revenue = 0.0;
}

While the names of the member variables are locked in this case, the type of value that they can hold is surely not locked.

Weak typing, with encapsulation

function Employee() {
  var name;
  var employeeCount;
  var revenue;
 
  this.getName = function () {return name;}
  this.getEmployeeCount = function () {return employeeCount;}
  this.getRevenue = function () {return revenue;}
 
  this.setName = function (n) {name = n;}
  this.setEmployeeCount = function (e) {employeeCount = e;}
  this.setRevenue = function (r) {revenue =r;}
}

This looks very similar to the stupid java way. There probably is a smarter way to achieve the same in JS but I am not aware of it. The more important thing to see is that while we have enforced constraints on the names of member variables, the actual contents of each member is loosely typed. However, it is possible to code in the type specific checks as part of the setters in the above code. The only annoyance of course is that there are no exceptions in the language and thus reporting and handling errors becomes tricky.

Python

Ultra loose typing (default)

Python is a strange language in the sense that while it does have support for OO concepts from the groud up, a class in python is essentially completely open ended. Here is what could be declared as a class

class Company(object):
    name = ''
    employeeCount = 0
    revenue = 0.0

However, nothing stops programmers from assigning values to previously inexistent fields of objects of this class. The class behaves like a map (a.k.a dictionary in python speak) in many ways. There is no requirement to consistently use a same data type for a given field nor is there any restriction on introduction of new members at a per instance level on the fly.

Weak typing, the wrong way

The following piece of code will ensure that members cannot be dynamically added to objects of a class

class Company(object):
    __slots__ = ["name", "employeeCount", "revenue"]

The reason why this is considered an incorrect way of achieving the goal is that the motivation for the introducing the construct of slots at the language level was to use it as a memory saving hint. It however does have the side effect that we need around locking down the possible set of member variables. There are a lot of programs that go against the spirit of the language and use the feature for this purpose

Weak typing, the right way

class Company(object):
    name = ''
    employeeCount = 0
    revenue = 0.0
 
    def __getattr__(self, name):
        raise AttributeError
 
    def __setattr__(self, name, value):
        if(name not in ('name', 'employeeCount', 'revenue')):
            raise AttributeError
        else:
            object.__setattr__(self, name, value)

Strong typing (uncommon, almost never done)

class Company(object):
    _types = {'name' : str, 'employeeCount': int, 'revenue': float}
 
    def __init__(self):
        self.name = ''
        self.employeeCount = 0
        self.revenue = 0.0
 
    def __getattr__(self, key):
        raise AttributeError
 
    def __setattr__(self, key, value):
        vartype = Company._types.get(key)
        if vartype:
            if type(value) == vartype:
                object.__setattr__(self, key, value)
            else:
                raise AttributeError
        else:
            raise AttributeError

Concluding remarks

It should be obvious by now that there are multiple ways to model an entity in almost every language. However, the default practice varies widely based on the language of choice. What some people do not realize is that choice with respect to degree of freedom or control is more cultural and less to do with languages. The SLoC needed to define an entity is actually more a function of this cultural choice that one tends to make as opposed to being a fundamental property of the language.

That being said, the language in question does matter to an extent and almost all these languages have gone through multiple iterations and the emphasis on what is most elegant & concise does seem to be shaped by culture. For example, trying to have absolute control in python feels very unpythonic. Likewise, a completely open ended solution in C++ also feels equally alien.

What has completely been ignored in this post the impact of these stylistic choices on the SLoC and maintainability of code that uses these definitions of the objects. That shall be another post for another day.

Posted in Uncategorized | Tagged , , | 1 Comment

Django middlewares, a strange way to do things

One of the pitfalls of being a polyglot is that it is easy to fall into the trap of drawing parallels rather quickly and incorrectly. In this post, we shall compare java servlet filters, wsgi middlewares and django middlewares.

The J2EE story

The notion of servlets is well understood in java, it is a piece of code that handles an incoming request and provides some response. The most popular kind of servlet happens to be the HttpServlet. Filters are powerful tools that are used to wrap a servlet to provide either a pre or a post functionality i.e. do something just before the servlet is invoked or do something right after the servlet is invoked. A few common examples of operations that usually configured as a filters are as follows:

  • Authentication
  • Output compression
  • Logging

And here is an example of the structure of a filter implementation:

public final class RealFilter implements Filter {
    public void doFilter(ServletRequest request, ServletResponse response, FilterChain chain) 
      throws IOException, ServletException {
 
       // Do the "pre" work
 
       // Now let the real implementation take over
       chain.doFilter(request, response);
 
       // Do the "post" work
    }
}

Things get interesting when multiple filters are used. A programmer is allow to stack any number of filters on top of a servlet. The “pre” parts of the filter are executed in order before transferring control to the servlet and the “post” parts are executed in reverse order. So if filters f1, f2 & f3 are configured in that sequence along with a servlet s1, here is what is really happening internally on each request:

f1.doFilter{
  // Do the "pre" work of f1
 
	f2.doFilter{
	  // Do the "pre" work of f2
 
		f3.doFilter{
		  // Do the "pre" work of f3
 
		  s1.service()
 
		  // Do the "post" work of f3
		}
 
	  // Do the "post" work of f2
	}
 
  // Do the "post" work of f1
}

As might have guessed, the invocation of chain.doFilter() from within a filter is crucial for this behaviour. It ensures that control is transferred either to the next filter or the servlet itself if there are no other filters to process. This paradigm has the following implications:

  1. It is possible to short-circuit the inbound path. Failure to call chain.doFilter() ensures that control never reaches the servlet and also filters that are further down the path
  2. It is not possible to short-circuit on the way out unless an exception is thrown and it is not getting caught by your filter
  3. The call stack gets deeper as you start adding filters. Examining the call stack from within the servlet will actuallly reveal all the filters

The actual servers (web containers, app servers, etc. etc) are permitted to introduce their own filters and add them implicitly. This however is not of interest to this discussion.

WSGI middleware

The python world has a lot of frameworks for developing web applications but didn’t have any standard , cross framework, cross server API for a long time. Though WSGI (PEP-0333) existed for a long time, it didn’t get traction until recent times. This twist in the evolution means that most application developers still code against their frameworks and wsgi’s utility has now been reduced to acting as a specification against which framework developers and python server implementors code against. Regardless, wsgi supports the concept of middlewares which operates pretty much in the same fashion as java filter

Django middleware

Django, a popular web development in framework also has the notion of middlewares. It happens to be one of those frameworks that got on the wsgi bandwagon quite late in the game (it did have some rudimentary support for quite some time but high quality support came in post 2009). Interestingly, django also has a concept of middlewares but it is quite different from anything else one has seen before. To understand the difference, let us first look into the structure of a middleware:

class MyMiddleware(object):
  def process_request(self, request):
     ...
 
  def process_view(self, request, view_func, view_args, view_kwargs):   
     ...
 
  def process_response(self, request, response):
     ...
 
  def process_exception(self, request, exception):
     ...

The biggest difference is that django middlewares are iterative and not stacked. The split interface for request and response is a kind of a giveaway of what is happening internally. Here is an oversimplified version of how middlewares are executed in the django world:

for i in middlewares:
	i.process_request()
 
invoke_the_view()
 
for i in reversed(middlewares):
	i.process_response()

Note that the rules for short-circuiting is much more complex than the java model and one must read entire documentation to understand those. So what are the implications of using iterative model as opposed to a stacked model?

  1. Depth of call stack is always fixed regardless of the number of middlewares used
  2. Short-circuiting is possible both on the inbound and outbound paths
  3. The stack frame (local variables) cannot be used to maintain context across “pre” & “post” phases for a single request.

 

The reason why I got writing down this post was reason #3. A common instrumentation practice is to usually have a filter that measures the time taken by a request. The obvious way to implement is to do the following steps:

  1. Start a  timer
  2. Do the actual work
  3. Stop the timer
  4. Measure the difference

Something as straightforward as this gets convoluted in the django way since there is no place available to store the context (short of polluting the request object). The added flexibility of being able to short-circuit even in the “post” phase also means that the instrumentation path could be skipped altogether. Overall, it definitely feels more complex than it should be.

tl;dr

If you are writing application agnostic middlewares for your django application, then you are probably better off just writing a wsgi middleware. Resort to django middlewares only if has something to do with application behaviour.

Posted in Uncategorized | Tagged , , , , | Leave a comment

Object composition implementation styles

 

In the first part, we looked at conceptual implications of the various styles of object implications. Now we shall look at a few common implementations of object composition in conjunction with the concepts presented in the earlier post.

Association v/s composition

First off, we shall start with an example in C to understand the difference

struct node {
  int data;
  node *next;
};

This is a fairly common definition of a node in a singly linked list of integers. Each node contains two elements: an integer and a pointer (logical reference) to the next node. The object layout looks as follows:

It is interesting to note that this logical layout would still be correct in most programming language implementations that have managed memory. Things get interesting when we go back to the definition of a rectangle as seen in the first post.

 

 

The difference should be fairly obvious: the rectangle in C contains two points whereas the rectangle in java contains references to two free-standing point objects. Again, note that the layout that is shown for Java actually holds true for any system where memory management is taken care of by some runtime. A non-exhaustive list includes, perl, php, python, shared_ptr in boost, etc. etc.

Implications of indirection

Additional usage of memory

The most obvious impact is that the rectangle class as implemented in memory managed style now uses two additional pointers to store references. This is the user visible overhead. There could also be a user invisible overhead in managing additional objects on the heap. To get an idea of what such overheads could be, one can look the implementation of heap allocation as described in “The c programming language” by K&R. Note that the overheads can be amortized by some very clever implementations or subsidized elsewhere but it does exist in some form or the other. The deeper the composition (i.e. object/struct tree is), the more of overheads we pay (both visible & invisible)

Slower access of fields

This is a lot more worrisome aspect than a larger footprint. Loading up of the rectangle object in memory does not mean that the referenced objects tl & br are also loaded into the same part of the memory. Here, the term generic memory is being used as opposed to RAM to signify any class of memory. For eg: it is possible that the rectangle object is sitting in the L1-data cache of the CPU whereas tl is actually sitting on disk since the page containing that object has been swapped out of RAM! In addition, an access to the logical top right corner goes as follows in case of indirection:

  • Load contents of base address of rectangle + offset to tl into say “r”
  • Load contents of base address of point (r) +  offset to x

In case of inline composition, it simply would be be “Load contents of base address of rectangle + (offset to tl +  offset to x) ”

Again, this overhead of jumping across various memory addresses due to a lack of locality of reference is proportional to the complexity of the object composition

Object copying/serialization

Another common problem with the indirection scheme is that it introduces the notion of shallow-copy v/s deep-copy. Most common implementations of object copying tend to do shallow copies. Explicit effort is usually needed to provide deep copy semantics. If in case, you have been reading this article as a C v/s Java thing, now is a good time to wake up. C++ programmers for example have always had to deal with “how deeply should we copy” problem whenever they chose to use an indirection scheme. In fact, the same is true even of C programmers except that they never had the option to overload the assignment operator and copy construction and hence, it always had to be controlled using documentation + special functions.

A variant of object copying is serialization. Serializing an object with indirections is usually a recursive descent problem given the non-continuous memory layout. Fully inlined objects can on the other hand can be serialized in one logical instruction that transfers a block of memory from one location to another destination.

 No memory sharing

Interprocess shared memory is a powerful concept in latency sensitive applications. Multiple processes can get a consistent view (including immediate write visibility) without the overheads of IPC. The presence of pointers/references however makes it near impossible to share such objects across processes without implementing a userspace level virtual address manager. This is so because, it is usually infeasible to map a given object to the same address space across multiple processes. Failure to do so means the references/pointers are no longer valid.

So why go through all of this?

The most common reason these days for choosing indirection over inlining is that most programming languages no longer offer the choice and the reason is automatic memory management becomes easier once we assume each sub-object has a life of its own. Should you happen to have a choice, then the question is if the sub-object is really a part of the main object or just something that the main object collaborates with. In case of a collaboration, again we have to resort to indirection. That being said, there clearly are situations where it does help to do have inlined objects.

Posted in Uncategorized | Tagged , , , | 2 Comments

Implications of object composition styles

Object composition is a concept older than object oriented programming itself. Let us start off with a well understood example of how to represent a rectangle on a Cartesian plane:

struct point {
   int x;
   int y;
} ;
struct rectangle {
   point tl; /* top left corner */
   point br; /* bottom right corner */
}

Here the rectangle object is a composition of two point objects and tl & br are sub-objects (not to be confused with sub-classing) of rectangle.

Revealing the sub-structure

Most objects end up revealing the state captured by their sub-objects in some shape or form. Writing a “java bean” that marks the sub-objects as private only to reveal them via setters & getters is effectively the same as having no visibility controls in place. The interesting question to ask is if the composing object allows programmers to interact with a snapshot of the sub-object or the actual sub-object itself. Let us once again go back to some code written in two different languages and see if you can spot the difference.

struct point { int x; int y; };
class rectangle {
   point tl; point br;
public:
   void set_top_left(point a) {tl = a; };
   point get_top_left() {return tl;};
};
class point {
  public int x; public int y;
}
class rectangle {
  private point tl; private point br;
  public void set_top_left(point a) {tl = a;}
  public point get_top_left() {return tl;}
}

The first snippet is written in C++ and the second one is in Java.  While the code looks identical, the behaviour of the two programs is completely different.

In the C++ version, the setter accepts a point and copies over its state onto the sub-object that represents the top-left point. Any manipulation of the argument by the caller after set_top_left has been invoked does not affect the state of the rectangle. Likewise, the getter returns a copy of state of the top-left point. Any changes done to the top-left point in the rectangle after the getter has returned is not visible to the caller. The reverse insulation also exists in both cases i.e. any changes done by the rectangle after the setter has been invoked is not reflected in the variable that was passed to the setter and any changes done to the variable holding the return value of the getter does not affect the state of the rectangle.

In the Java version, no snapshotting occurs. For example: if the caller chooses to update the abscissa of value that it passed to the setter, then the rectangle would also see the update. The assignment is not a transfer of state. Instead, it is merely transfer of responsibility to some other object.

It is perfectly possible to implement either kinds of behaviour in both languages, it just so happens that the most simplistic (and natural) style of coding produces different results. The exact means to mimic the “other behaviour” is left as an exercise to the reader.

Are sub-objects the same as free standing objects?

Often times, programmers tend to forget the difference between a class and an object and also implementation details from core concepts. Try and answer the following question to see if you understand the difference: “Does the top-left corner of a rectangle have an identity and existence outside of the rectangle?”

For starters, the notion of a top-left corner itself is very questionable. It comes into play only if we are to assume that the edges of rectangle are parallel either the x or y axis. In effect, any point that needs to be treated as a top-left corner of the rectangle is only valid as far as a specific implementation of the rectangle is concerned. Unfortunately, this is not the main topic of the post. We shall instead spend more time on the existence part of things. Point, as a concept, can clearly exist without rectangles as a concept. A specific instance of point, say (3,5 ) can also exist without a rectangle. The same co-ordinates (3, 5) can also be a vertex of a rectangle. However, it does not mean that a free standing point (3,5) has the same utility as a vertex (3,5) that is the top-left corner of a rectangle has.

A piece of code that is logically expecting a top-left corner of a rectangle can potentially fail if it is given an arbitrary point. Protection against such failures is usually managed by carefully structuring code paths. One must realize that the semantic type of these entities are different enough though the user-defined data type happens to be the same. This causes a lot more problems than one would anticipate. The most perplexing question is can a vertex of a rectangle outlive the rectangle itself?

The answer is not unless it is semantically casted to something else. As mentioned earlier, this is usually not possible to express this, at least conveniently. This causes weird situations if the designer of the rectangle class has chosen either to use an otherwise general purpose point to represent its vertex or has directly exposed the underlying vertex to the outside world. The former case is not so troubling as the latter one and here is why. Try answering the question “What happens to the leaked/revealed vertex after the rectangle dies?”. If we are still able to meaningfully use that object, then it is because we have done a semantic cast that is enabling us to use it in a different context. If not, subsequent operations that we would perform is gibberish. Having a memory managed runtime usually makes it very hard to appreciate this aspect since the object as understood by the language continues to remain valid and hence one finds it that much more harder to spot the issue.

What does it really mean?

In short, if you choose to directly reveal a live sub-object as opposed to a snapshot, care must be taken to ensure that code that is operating on the sub-object understands the lifecycle of the containing/composing object. Just because your runtime guarantees that there will be no memory corruption/leaks occur does not mean that you can be sloppy. If you are still a non-believer see the code below and spot the trouble for yourself.

class TopMostPointSeeker {
   private List pts = new ArrayList();
 
   public TopMostPointSeeker(List rs) {
      if(r == null || r.size() == 0) {
         throw new RuntimeException("Need non-empty collection")
      }
      for(Rectangle r :rs) {
         pts.add(r.get_top_left());
      }
   }
 
   public getTopMost() {
      /* Implementation delinked from list of active rectangles
       * May not return the topmost point at a given instance.
       *
       * Nothing in the externally visible interface reveals this feature/bug.
       */
      Point retval = pts[0];
      for(Point p: pts) {
         if(p.y &gt; retval.y) {
            retval = p;
         }
      }
      return retval;
   }
}

Wait for part 2 of this story where we look at the most common implementations and its related implications.

h3

Posted in Uncategorized | Tagged , , , | 4 Comments

In search of a job queue

Job queues are an essential element in internet application design to execute long running tasks. This stems from the fact that web servers and consequently web applications are best suited for interactive applications. If a particular operation that needs to be carried out fits the description below, then it makes a good case for the usage of job queues

  • For the most part, these tasks need to be carried out near instantaneous fashion. Specifically, the commencement of execution of the task should happen at the earliest possible time. The expectation of completion however depends on the nature of task.
  • If the task cannot be executed immediately for some reason, it should be queued up and processed later.
  • Executing the task is resource intensive in some form or the other.
  • Tasks once submitted must not be dropped to the extent possible.

The desirable features of a job queue are as follows:

  1. The job queue should have durability.
  2. The queue should support multiple producers & consumers. These queue operations would be performed across hosts.
  3. The draining of the queue should happen as quickly as possible. If a new task gets added to the system and there are idle consumers, the consumption should commence at the earliest.

The first two points are well addressed by an RDBMS solution. However, it struggles to achieve the third point since there is no inherent notification mechanism and aggressive polling is the closest solution but it does not scale very well. A message queue is good at supporting the last two points but trying to maintain a credible state is exceptionally hard. Interestingly, the popular job queue solutions out there choose to use either an RDBMS (example: gearman) or an MQ (example: celery). However, a mix of both seems to be the right answer. I shall briefly describe what looks like.

Adding a new task

  • Add a new element to your data store. This element should represent every aspect of the task such as the task type, the task details and also task management data such as execution status. A unique id must also be generated by the producer before adding the task to the store. Failure to make this entry is considered as failure to accept the job.
  • A notification event is sent out a message queue. The notification contains the task type and task id.

Processing a task, the normal case

  • A pool of consumers is actively waiting for notification of a new task and starts working the moment it gets a notification. The delivery mechanism of the notification can be configured to either exactly one or at least one consumer based on what looks like the right trade-off.
  • The consumer checks with the data store and manipulates it accordingly to indicate that it has voulenteered to perform the task.
  • When it is done processing the task (either successfully or unsuccessfully), it updates the store with the outcome.

Processing a task, the abnormal cases

  • The notification message could have gotten lost and not reached any consumer for a variety of reasons. It is necessary to sweep the job queue periodically for any unprocessed tasks and trigger its execution. The latencies associated with this is comparable to a pure RDBMS based queue. Specifically, the need to scan by the value of a field (task status) ni addition to the normal access pattern based on id is what makes RDBMS a convenient choice.
  • Semi-completed and also failed tasks may have to be retried depending upon the semantics of the task at hand. This might require a back-off mechanism which will effectively need a scheduler. In such situations, the scheduler needs to be held outside of the job queue to achieve clear separation of responsibilities.

So far, I have not been able to find any open source solution that seems to follow the above approach. If you know of any, do let me know. Else I get down to implementing one.

Posted in Uncategorized | Tagged , | 1 Comment

An introduction to the elements of thrift serialization

Apache thrift is a surprisingly popular data serialization and RPC library. I say surprising because at the time of this writing, there is hardly any decent documentation out there that explains the elements of thrift serialization. It is however easy to find tutorials that help you hit the ground running very fast. This article assumes you are conversant with simple examples.

Tbase objects

Data structures are defined using the thrift IDL. Code is then generated using this IDL in some programming language. The generated class usually inherits from a type known as TBase defined in the thrift library. Objects of type TBase are the ones that can be serialized or deserialized.

Protocols (Serializers)

Strictly speaking, modern day thrift (0.5 at the time of this writing) is a pluggable serialization library rather than being a specific way of serialization. The original format is simply called the  binary protocol (class name TBinaryProtocol).  Other available protocols are the compact protocol and JSON protocol. The job of a protocol is to convert a TBase object to and from a byte stream.

Transports

In thrift speak, a transport is a place where the serialized representation of an object is written to (or read from in the case of deserialization). Since the motivation for serialization tends to be either persistence or a network transfer, it is not surprising to find a transport for a generic stream (I/O stream transport) and more specialized versions of it for various kinds of network endpoints. A memory transport is also available for applications that wish to work off a memory representation of serialization. While most transports will pass on the output for a serializer as is, a transport may choose to alter the byte stream as it pleases. The most common usage is byte addition for message framing. Serializers in general, do not produce message boundary markers. If multiple objects need to be used in conjuction with streams, it becomes convenient to have message boundary markers. The framed transport is a good example of a transport that does exactly this kind of byte addition.

Piecing it all together

An object of a transport is created and it is associated with a protocol object.  This protocol object can now be used in conjunction with Tbase objects. TBase objects have  read() & write() functions that take a protocol object as an argument. Thrift also comes with seemingly tempting utility classes called TDeserializer & TSerializer.  They are however not the best choice since they tend to be restrictive in terms of the choices of transports and protocols. Here is a pseudocode sample to illustrate the usage pattern:

class Point inherits TBase
{
  int x
  int y
}

Point obj

FileStream ifs = open("path to file", "r")
TBinaryProtocol tpl(TIOStream(ifs))
obj.read(tp1)

obj.y = 100

FileStream ofs = open("path to file", "w")
TBinaryProtocol tp2(TIOStream(ofs))
obj.write(tp2)
Posted in Uncategorized | Tagged | 1 Comment