Jonathan's Technology & Finance Blog

Giant Groovy Scripts and Enterprise Software Forensics: Tricks and Treats

2010-12-04T17:43:00.002-05:00

The Vision

How often would it be helpful to record everything a complex system did at a critical moment, be able to log the information intelligently, be able to play it back at some point in the future, and have a record to fall back on that could re-create the state of the system at a given point in time?

I find myself investing a lot of time studying the log files -- sometimes poorly constructed or lacking critical information -- of real-time systems, build systems to simulate typical and exceptional moments in the financial markets, and instrumenting existing systems to better combine the insights of forensic analysis with simulation.

The questions I started with are, admittedly, a set up for a discussion of proxies that write their operations to a script while executing production code, thus creating a human-readable and machine-executable record of exactly want took place during operations. In Java, this is easily implemented by combining multiple implementations of a given interface (one that record and one that executes) with a delegation class that receives the original instructions and provides handlers for exceptions and so on.

In Groovy, it is easy to accomplish the same thing using Groovy's Meta-Programming features (for which there are already many good blogs and presentations).

However you choose to implement the code-generation part of a component that records a given execution path and its inputs, you are likely to hit certain snags. That said, if you started down this path there is probably a reason and my conclusion is that it is worth the pain. The forensic value in having a human readable / editable "log file" that can also be evaluated to reproduce the exact state of a system at a given point in time cannot be undervalued.

Practical considerations for very sizable playback scripts

There are a number of problems with this approach as it related to context specific business logic, external state management, exceptions and errors. In my situation we have a point-in-time database so I can send any query to the database with an additional parameter that specifies an effective date and the query will return the information that was available to the system at that point in time. This solves most of the state management issues not already serialized to my scripts. For the purposes of this post, I will focus on mechanics on dealing with the gigantic scripts you have produced.

In my case, the generated script have the feel of database operations. For example,

api.beginTrx()
  inst.defineInstrument(
    [ name : 1.23, type : 'sample', avg : 3.1415927], 
    [ 5 : '', 7 : '', 9 : ''])

  inst.defineInstrument(
    [ name : 1.23, type : 'sample', avg : 3.1415927], 
    [ 5 : '', 7 : '', 9 : ''])

  inst.defineInstrument(
    [ name : 1.23, type : 'sample', avg : 3.1415927], 
    [ 5 : '', 7 : '', 9 : ''])

api.commitTrx()

The first round of difficulties came from compilation errors with either the code or with data serialization.

When considering these, it is important to realize a few things about how Groovy works with the JVM. First, although many interpreted and dynamic languages evaluate their code one block at a time, Groovy's runtime compiles the entire script at once into a class derived from the abstract class groovy.lang.Script. At this point the script can be compiled in a variety of ways ranging from the GroovyShell or GroovyClassLoader. Additionally the GroovyScriptEngine can both compile and evaluate a scrip with a given binding for external variables and keep class files in synch when the source code changes.

This difference between Groovy and a language like Perl which does not compile the entire script, is that your code generation component must produce syntactically valid Groovy for every possible combination of execution paths and state migrations. Obviously, this was already a requirement because the goal of this approach was to be able to replay exactly what happened in a large and complex system. My point here is that a small compile errors in the generated code will have much more unforgiving consequences in Groovy than in some other dynamic languages because the entire script is compiled at once. That said, if your goal is to have defect free code in this feature point, then consider the compilation process a blessing.

If you are using Groovy's meta programming features, this requirement is fairly easy with respect to method invocation and such. Typically the bigger program in my experience involves how to best serialize the data such that it will replicate state accurately, be human readable, and be machine evaluable. In most cases their are ways to construct a string that, when evaluated, will reflexively re-create an object with the same state. A slightly trickier problem is when to evaluate and when to serialize GStrings. Here thorough unit testing and integration testing will be key to your success. You can see some of my early thoughts on these problems in the first two posts I made on Groovy Object Interchange data files.

Although using the dynamic groovy support classes provide powerful features, once compiled the run method defined in the new .class file call be called on any instance directly from Java. So the point to keep in mind here is that all the code from your script will get folded into a method that will be invoked through Groovy's run methods.

The JVM 64k Problem For Large Groovy Scripts

Additionally, the JVM class file specification has a 64KB limitation of the size of a single method. Typically when a script is compiled, you should assume that the totality of the code generated by your script will reside in a single method. Therefore, it won't be long before you find yourself on friendly terms with java.lang.ClassFormatError. The database-like example above will quickly result in this. In that example, each line of code contributed about 10 bytes of Java bytecode to the primary method and, predictably,

If you read the various threads on this error, the suggestions that seems to be among the most popular revolve around refactoring your code into a series of smaller method invocations and occasionally around how to automatically check the implied method size prior to compilation and safely divide the script into a number of methods that could be evaluated individually.

To this I have two responses. The stated goal here is to accurately re-create and document an execution path, so it would be unexciting to add additional structure that did not exist during real-time evaluation. Secondly automatically decomposition of the primary method is not as trivial as it sounds (and if it is, should then be part of the parser / compiler).

That said, Groovy does not constrain you to a world of small, reasonably sized scripts.

Closures and Builders are Your Friends

Consider the simple alternative to the above code:

api.transaction {
  inst.defineInstrument(
     [ name : 1.23, type : 'sample', avg : 3.1415927], 
     [ 5 : '', 7 : '', 9 : ''])

  inst.defineInstrument(
     [ name : 1.23, type : 'sample', avg : 3.1415927], 
     [ 5 : '', 7 : '', 9 : ''])

  inst.defineInstrument(
     [ name : 1.23, type : 'sample', avg : 3.1415927], 
     [ 5 : '', 7 : '', 9 : ''])

  inst.defineInstrument(
     [ name : 1.23, type : 'sample', avg : 3.1415927], 
     [ 5 : '', 7 : '', 9 : ''])

  inst.defineInstrument(
     [ name : 1.23, type : 'sample', avg : 3.1415927], 
     [ 5 : '', 7 : '', 9 : ''])

  inst.defineInstrument(
     [ name : 1.23, type : 'sample', avg : 3.1415927], 
     [ 5 : '', 7 : '', 9 : ''])
}

Here the body of the transaction is contained in an anonymous closure which could be passed to a method with the signiture:

def transaction ( Closure body ) {
    beginTrx()
    try {
      body.run()
      commitTrx()
    } catch (Exception e) {
      rollbackTrx()
    }
}

Here the body of the short transactions are wrapped, not in begin / commit method invocations, but in an anonymous closure that generating into its own class changes the practical limitations considerably. Still, each top level method invocation adds additional bytecode to the principal method and this example above now scales to 2,000 / transactions or 25,000 lines of code before failing. Larger transactions would have let the file grow still larger and nested transaction allowed yet more.

Moreover, packaging up units of work into larger baskets and submitting the baskets to a smart transaction manager has some appeal on its own terms.

The Most Powerful Tools Come At A Price

The last thought I would like to share is that for extract-transform-load data flow scenarios, this approach proved incredibly powerful. In the end, I had a small code base that would allow be to examine without binary structures or obscure references all of the data flowing into and out of a complex system, to be able to re-examine the system at a given snapshot, and to be able to re-generate the system from its first execution to the present day using the replay tool. But these features came at a price.

I spent a lot of time tweaking the script generation tools and script execution runtime.
I spent a lot of time making sure that everything beyond simple collections and primitives serialized correctly
I spent more time than I should studying the internals of the VM and groovy bytecode generation, but admittedly that is partly because I like that stuff.
I had to redesign the Core APIs of the 'live' system to be able to properly support simulation and playback, although I believe I ended up with a better API for the 'live' system as well

Steps Required To Fully Implement This Vision

Scripts would have to know which version of the codebase they ran against. I would probably narrow the specificity here for major.minor version releases, allowing a patch release to re-write history by fixing a bug in a minor release. The script runner would build a classpath appropriate to the system executing at that time
Database versioning would have to be explicitly synchronized with codebase versioning and simulations run against the "old" schema would have to execute "correctly"
State would have to be explicit with few or no side effects such that the serialization mechanism for the code producing agent would be able to exactly capture both the initial state of the system and all flows of data that changed that state.

Inspect() / Eval.me()

I have made this point previously, so I won't invest too much in this, but much of what I built is remarkably similar to Groovy's inspect() / eval syntax, but for that to work properly support for common Java datatypes -- Date classes in particular -- and a more generalized contract for POJO / POGO objects to Inspect() themselves (which people could override when advanced state management or systems integration logic was required). This functionality is clearly both within the syntactical aspirations of the language and within its approach to dynamicism. It is also well within the abilities of the current team

Groovy and The Beauty of The Half Baked Idea

As I have said before, one of my favorite aspects of the Groovy eco-system is the speed and ease with which it allows someone to build out a half baked idea and begin to get serious about it. Most of the fully baked ideas in the world have already found their way into great software. Most of the great ideas of the future are half-baked ideas today. Not only does Groovy let you get the half baked ideas into some kind of working structure that allows for refinement and rigorous clarification, but it also allows an idea to fail quickly. This is important also because most of the half baked ideas are bad ideas and the quicker you can move onto the next one the better.

As strong an advertisement as this is for the language, the eco-system, and, really, the Groovy community, it is also evident in the eco-system itself. Inspect() and Eval() feel, to me, like half baked ideas that got half finished before someone got pulled into something bigger and more important. There are a fair number of points in the codebase where there are diamonds in the rough waiting to be attended to. There are also a fair number of ideas that should have died young but are now stuck in the codebase. And there are others (like the very attractive Grails-UI Rich Internet plugin) that were great at one time but now need work but have now been abandoned by their authors. This is common enough is strong and active open source communities -- think Apache, JBoss and so on -- but Groovy is hitting a critical mass right now in terms of its support all around the world and is also being challenged as the Java language adopts more and more of its most popular features.

Groovy Data Interchange Format

2010-09-17T17:19:00.000-04:00

Groovy Object Notation ? GrON?
I Guess it had to happen...

Currently I spend a lot of time building DSLs in Groovy that will get used by other tools, so writing code that generates syntactically correct Groovy -- and in particular being able to produce machine-executable / human-readable text files that serialize data acquired somewhere else is really important...

Therein we find one of the problems with Groovy (as opposed to some other functional and dynamic languages). There is no simple and consistent way to write data to a file that will eventually get passed to XXX.parse on GroovyShell or GroovyClassLoader or passed to GroovyScriptEngine or passed to Eval.me(...) and return an equivalent structure:

Simple map to string semantics use double-quotes for Strings without escaping dollar sign characters ($) that will get caught up in GStrng evaluation.
ConfigObject and ConfigSlurper come very close but

a) have different syntax
b) do not handle Date and some other objects correctly
In some cases you can fix problems with serialization of complex types with overrides on toString in the metaClass, but some classes do not allow overrides on toString (e.g. overrides where Date.metaClass.toString={->return new Date(...) } doesn't really work either...

So, even though there is probably some class deep in the API that does this, I dug up some old code that wrote out data structures as Groovy code. Looking at this as a first class service for DSL language development, I would propose a set of requirements rather than my sample code. The requirement would be thus:

Be able to handle primitives, basic collections, strings, booleans, and Dates
Get the time-zone handling correct on the Date implementation
The serialization tool should generate human-readable / machine-executable code (Groovy syntax correctness is a given)
Eval.me(script) should, for all practical purposes, be the inverse function for writeObject(obj) -> String. String java equality won't apply for collections, but for the sake of these discussions we will allow two collections of the same type with functionally equal values to be equal collections
Complex types should be able to handle their own serialization / de-serialization if they choose to.

So, this is what I coded up for a first cut. If anyone knows a where this functionality already exists in the GDK, please let me know. Any enhancements of functional improvements would be welcome also.

 
class GroovyObjectNotation {
    private String dateFormatText = "yyyyMMdd-HH:mm:ss.SSSSS Z"
    private SimpleDateFormat dtFrmt = new java.text.SimpleDateFormat(dateFormatText)

    public writeList(list) { 
      return "[ " + list.collect{ t -> writeObj(t) }.join(", ") + " ]" 
    }

    public writeSet(Set set) {  
      return ("new LinkedHashSet( ${writeList(set)} )").toString(); 
    }

    public writeMap( Map map) { 
      return ('new LinkedHashMap( [' + 
         map.collect { k, v -> 
            "${writeObj(k)} : ${writeObj(v)}" 
         }.join(", ") + '])').toString() 
     }

    public writeNumber(Number obj) {
        if (obj instanceof Double) return "${obj}d";
        if (obj instanceof Float) return "${obj}f";
        if (obj instanceof Integer) return "${obj}i";
        if (obj instanceof Long) return "${obj}L";
        if (obj instanceof BigInteger) return "${obj}g";
        if (obj instanceof BigDecimal) return "${obj}g";

        if (obj instanceof Short) return "${obj} as short";
        if (obj instanceof Byte) return "${obj} as byte";
        return obj;
    }

    public String writeDate( obj ) {
        if (obj instanceof java.sql.Timestamp) 
          return 'new java.sql.Timestamp(Date.parse(\'' + dateFormatText +
              '\',\''+dtFrmt.format(obj)+'\').getTime())'
        else if (obj instanceof java.sql.Time) 
          return 'new java.sql.Time(Date.parse(\'' + dateFormatText + 
              '\',\''+dtFrmt.format(obj)+'\').getTime())'
        else if (obj instanceof java.sql.Date) 
          return 'new java.sql.Date(Date.parse(\'' + dateFormatText + 
              '\',\''+dtFrmt.format(obj)+'\').getTime())'
        else if (obj instanceof java.util.Date) 
          return 'Date.parse(\'' + dateFormatText + 
               '\',\''+dtFrmt.format(obj)+'\')'
        else if (obj instanceof java.util.Calendar) 
          return 'new GregorianCalendar(Date.parse(\'' + dateFormatText +
               '\',\''+dtFrmt.format(obj)+'\').getTime())'

        else return obj.toString()
    }

    public writeObj(obj) {
        Object.metaClass.toGroovyCode={-> delegate.toString() }
        if (obj instanceof Date || obj instanceof Calendar) return writeDate(obj)
        else if (obj instanceof Number) return writeNumber(obj)
        else if (obj instanceof Set) return writeSet(obj)
        else if (obj instanceof List) return writeList(obj)
        else if (obj instanceof Map) return writeMap(obj)
        else if (obj instanceof Boolean) return obj ? true : false


        def retVal = obj.toGroovyCode() == obj.toString() ?
            "'" + obj.toString().replaceAll('([^\\\\])\'','$1\\\\\'') + "'" :
            obj.toGroovyCode()

        return retVal
    }
}

Groovy Math II: The Monte Carlo Engine

2009-05-31T17:58:00.000-04:00

Code update can be downloaded here

In the last post, I introduced a Groovy numeric collections class that supported basic algebraic operators and would execute those operations in parallel. It is just one class (plus a Java helper class that maps the reduced data into tasks). Why am I excited ?

It could be, I envisioned, a power component for a Monte Carlo engine. This would a have certain a certain simplicity for researchers and strategists who wanted a platform around which they could articulate financial math. It would allow for arbitrary path generation and for stochastic processes that might or might not conform to the log normal distribution that dominates much of financial mathematics. It would be able to price not just one option but an entire options chain for a given expiry. It would also be able to provide an arbitrary convergence measure.

So today I uploaded to GitHub a MonteCarlo pricing engine, a number of financial business logic classes for option payouts, path generation, yield curves, and so on. The pricing engine takes the stochastic variable generators, the asset path generator, and the convergence test as closures allowing for the financial professional to use simple closures to do the job. The contract:

Stochastic Process: The implicit contract is that the random number generator provides a NumericGrid of random numbers large enough to price the options correctly. Monte Carlo simulations are good for high-dimension problems and it is easy to envision a requirement that the random number generator might produce several grids (Asset Price Movement, Stochastic Volatility Values, Stochastic Interest Rates, Poisson Processes, etc...) In this model, one of two contracts must apply. Either the random number generator must generate all of the variables required for the algorithm or the algorithm must produce the additional stochastic terms. Because both processes are closures, the author can pretty much do what they wish. The only requirement is that the closure for the path generator be able to accept the output from the random number generator. Finally because the grid is by definition a complete distribution there is no requirement that is conform to a named mathematic distribution, so the author could add additional kurtosis or extreme event values to their heart's content.
Path Generation: This must accept this output of the random number generator and return a NumericGrid of paths. This will feed the options chain.
Options Collection: Must implement a method called payout that accepts path input. Accepts one or more paths as inputs and returns a object of the same class and the path input as a result.

One of the virtues of of setting up the core components as closures is that they can be overridden to accommodate special circumstances. The default implementation:

  
def convergenceTest = { size, standardDeviation ->
  standardDeviation / Math.sqrt(size)
}

Applied the Central Limit Theorem to estimate the price accuracy of the model as a function of the population size and the standard deviation estimate for the sample. This has the unfortunate but inescapable effect of requiring the engine to increase the path size by a factor of 100 to realize improvement in pricing accuracy by a factor of ten. This is an appropriate assumption for pseudo-random normally distributed paths.

However, the NumericGrid class has a handy method that produces a low discrepancy sequence
appropriate for Quasi-Random variables and in this case guaranteed to be complete discretization of the distribution over a space of that size. This will allow the engine to converge more quickly such that our initialization code can do the following:


MonteCarloEngine engine = new MonteCarloEngine()
engine.convergenceTest = { size, standardDeviation ->
  standardDeviation / size
}

I will explore some more of the class library later on, but a simple view into the Monte Carlo engine would be the following script:


 MonteCarloEngine engine = new MonteCarloEngine()
 engine.convergenceTest = { size, standardDeviation ->
    standardDeviation / size
 }
 engine.timeHorizen = 1.0

 def strikes = [80, 90, 100, 110, 120]
 strikes.each { strike ->
   engine.options << new SimpleOption( strike : strike, 
      payoutType : PayoutType.Put, name : "${strike} Strike 1 Yr Put" )
   engine.options << new SimpleOption( strike : strike, 
      payoutType : PayoutType.Call, name : "${strike} Strike 1 Yr Call" )
 }

 def brownianMotion = new LogNormalPathHelper(spot : 100, 
      vol : 0.15, rate : 0.05, time : 1.0)
 def closure = { random ->
   brownianMotion.generatePaths(random)
 }
 engine.pathGenerator = closure

 def options = engine.runSimulation()
 options.each { option, price ->
   println "Contract: ${option.name} was priced @ ${price} over ${engine.size} iterations"
 }

 ParallelMathHelper.shutdownPool()

Groovy Math I: Parallel Calculation

2009-05-29T10:22:00.000-04:00

Functional Programing and Numeric Computing

(Project page at GitHib is Groovy Numerics Repository)

What if we would write Monte-Carlo Simulations like this ?

def normalRandom = ... // get stochastic terms from somewhere
def operation = { random ->
return 100.0 * Math.exp((0.05 - 0.15 * 0.15 / 2.0)+ 0.15 * random)
}
def paths = operation(normalRandom)

This entry will be the first in a series of articles following up on my presentation at the GR8 Conference on Groovy, Grails, and Griffon. In the first set, I hope to discuss high-performance mathematical operations beginning with Numeric Collections and subsequently with a linear algebra library / DSL and finally with root solvers. In the second set, I will discuss distributed calculation in a grid computing environment and the the final set I will explore issues related to distributed caching.

The ultimate destination for the journey will be two assets that work in partnership. Together they will be called DASEL a DSL for financial engineering.

The first asset will be a number of small building blocks for our DSL. The main elements of this language will be submitted in the next few entries.

The second asset will be a distributed cache that could accommodate a comprehensive model for the global financial eco-system. It would will allow dynamic enhancement of the 1st class objects and data model. It would allow dynamic enhancement of the mathematical models. It would allow the developer / analyst / trader to find first class objects through simple queries and traverse the data with simple tree like logic. It would be able to populate itself and recover lost reference and time series data.

In this entry, I will explore the simplest use case: A simple mathematical expression that gets evaluated many times with some (or all) of the inputs changing with each evaluation.

This kind of use case might not strike most people as a likely candidate for Groovy -- or any other scripting language for that matter. If performance is key, shouldn't this sort of thing be coded in C++ or at least Java? On this question, I will concede the main point for the most performance hungry applications in the financial universe: automated market makers and high-frequency arbitrage. These application often require sub-millisecond responses, co-location at the exchanges, and their profitability is driven as much by the fill ratio as it is by identifying the correct trading signals. However, if we relax the requirements just slightly, we find this dynamic language (running on top of a a second interpreter, the Java VM) out performs naive Java and C++ implementations even on a single dual-core CPU. Even looking for a more rigorous benchmark, I hope to show that Java and indeed a Groovy-based DSL for dynamic expression evaluation will both come close to the high-performance benchmarks set in those languages but also to show that high-performance dynamic programming is possible and -- with a little help -- straightforward.

If this aspiration is achievable, they the benefits of using a dynamic language for idea generation, analysis, and research becomes a no-brainer. Researchers can explore an idea using purely mathematical notation, the expression will enter the eco-system as a closure, and the back-end components will worry about the performance side of this -- presumably through a combination of optimizations, intelligent dependency management, and parallelism. Complex multi-variant time series analysis and problems of dimensionality reduction for multi-factor models become a problem domain that does not require weeks of C++ coding. Rather the scripting platform becomes the white board of half-baked ideas that are quickly sent to the trash can for qualified for more rigorous study.

The first artifact presented will be a numeric collections class. It is similar in metaphor and structure to a matrix class. Internally it is a two dimensional array of values. The key difference will be that it will follow the rules used for conventional algebra rather than linear algebra, but will do these operations in bulk rather than serially. For example, consider the log normal random walk model commonly used for the stock market:

We can use the Euler method to create an analytical solution for S(t) as follows:

Now the question revolves around where we get our random numbers, how do we iterate through them, and how many iterations to we need to converge on a reasonably good price?

This is where Groovy kicks in. Traditionally this is done by looping through a simple expression where by each iteration is seeded with a different random number. Our groovy class will treat the entire collection as a number, evaluate each term in the expression following the normal rules of operator precedence, and return a new collection (of the same size and shape as the original) that has the final result of the expression using the initial value as the seed.

For those used to thinking about these kinds of expressions using linear algebra (which will be the subject of the next post), this will seem both familiar and counter intuitive. The operations that combine a scalar and a collection will be the same as the matrix arithmatic they are familiar with. The collections multiplication --I use the term grid to referrence a 2 dimensional collections class that support conventional algebra and a matrix for a collection that implements linear algebra -- is the different. In the grid class, the resulting collection is the same size as the original grid. The resulting component (i,j) is that product of the i,j component in grid A and the i,j component in grid B. This is accomplished using Groovy's operator overloading capabilities. Under the hood, since each row vector can be processed independently, a thread pool will execute the operation over each row vector as a discrete task and a helper class written in Java will create the Callable for each row vector. This will have several advantages over the traditional 'for loop.'

If the expression combines scalar values and collections, the scalar portions will only be calculated once and the result will be applied to the collection. Normal operator precentance and a little bit of smart grouping will replace the task of decomposing the expression programmatically or building out a dependancy graph.
The JIT and CPU Cache are good at optimizing similar operations executed in sequence. Asking Mr. CPU to calculate 2 ^ x over 1,000,000 iteration might result in loading 2 into register A and x into register B and then executing the power function. If we can keep 2 in A and load 1,000,000 values for X into the cache, the result will come faster. If we are talking about 2 ^ x + y, we are still better off calculating 2^x over 1,000,000 inputs, and then adding 1,000,000 y-s to 1,000,000 x-s than doing 1,000,000 separate loops for 2^x + y.
The expression can be entered as a closure and the author does not need to know what the strongly typed characteristics of the variables will be so long as they support the familiar operations.
The operations are done in parallel by default without additional code

So the first step of our Math DSL has some obvious requirements:

It should store a collection of values
It will need to implement plus, minus, multiply, divide, power, etc for both use cases involving scalar values and other (same size, same shape) collections
It will need to enhance the Number.metaClass to allow scalar values to support operations with Numeric Collections as operands
It would be nice to provide collection supporting overrides for max, min, exp, power, and so on from static Math.* methods
It will need a helper class that manages a shared thread pool for computational tasks
The helper class will provide simple routines to reduce the two dimensional array of values to a collection of Callable tasks that can be submitted to the thread pool.
The collections class will support additional helper methods (statistical methods, factory methods, etc...) to the extent they support a clear API.

Now, let's return the the Monte Carlo simulation. Using the Euler method described above, we should be able to code something like.

import com.dasel.math.NumericGrid

def gaussian  = NumericGrid.createQuasiGaussian(1000,1000);

def eulerMethod = { price, time, rate, vol, rand ->
def rets =  (rate-0.5*vol*vol)*time + Math.sqrt(time)*vol*rand
price * Math.exp(rets)
}

def model = eulerMethod.curry(100.0,1.0,0.05,0.15)
def paths = model(gaussian)

Here, with a few lines of code. We have evaluated the the "model" expression 1,000,000 times.

Benchmarks: Naive Java versus Smart Groovy

It is always unfair to present a naive implementation of a straw man design and a sophisticated implementation of your 'favored' solution. The reason I will defend this slight of hand is that performance is not my end goal. Performance is a necessary condition, but flexibility and speed of development are the key drivers. A sophisticated C++ or Java developer would be able to beat my benchmark, maybe by a factor or 2 in Java, maybe a factor of 3 or more in c++ (I think that this would take an exceptional developer in c++ and they would need to work much harder than I have to accomplish it, but take this as a challenge and prove me wrong). Gauntlet thrown, let's see how me did on my Vista laptop with 1 dual core CPU.

On the Java side, I went for simplicity. No generalized support to evaluate an arbitrary expression. Single threaded. Constants over variables. The Java solution did not store the results anywhere, the values where simply discarded. The only output was the time required to execute the loop. Also the drift component for the Euler model is explicitly calculated before the loop begins, reducing the number of operations roughly in half. The benchmark code went as follows:

public static Double test(List values) {
long start = System.currentTimeMillis();
double drift = 0.05 - 0.5 * 0.15 * 0.15;
for (Double value : values) {
double diffusion = 0.15 * value;
double result = 100.0 * Math.exp(drift + diffusion);
}
double time = (System.currentTimeMillis() - start) / 1000.0;
System.out.println("Time = " + time + " seconds");
return time;
}

public static void main(String[] args) {
List values = createrDistribution(1000000);
long start = System.currentTimeMillis();
List benchmarks = new ArrayList();
for (int i = 0; i < 100; i++) {  
benchmarks.add(test(values)); 
} 
double avg = (System.currentTimeMillis() - start) / 1000.0 / 100.0; 
double min = Collections.min(benchmarks); 
double max = Collections.max(benchmarks); 
System.out.println("Min: " + min + " Max: " + max + " Avg: " + avg); 
}

So, in the end the Groovy version executed the path of a arbitrary stock market issue over 1,000,000 different one year paths with constant volatility and a constant interest rate 100 times. The first execution was dramatically slow then the subsequent realization s, taking on average just over 1.1 - 1.3 seconds to complete. The average execution time, however, quickly converged to roughly 110-130 milliseconds with a best performance in the 100-120 milliseconds range for a sample size of 1,000,000 draws. The Java sample had a best performance of 150-160 milliseconds and an average that converged very quickly to roughly 180-190 milliseconds. It, too, showed additional sluggishness in the first iteration although it was far less significant than the early Groovy iterations and faded more quickly. I doubt very much that a dual core CPU would ever realize a performance improvement of order two (linear scaling) simply by adding an additional thread, and I cheated a little but in Java's favor by discarding the results and pre-calculating the drift component and thus reducing the total number of operations. All in all, I think that this shows two things:

Performance in numerical computing between Java and Groovy can be a wash
There are some aspects of the operator overloading capabilities that when combined with a collections class lend themselves to serious performance gains from the JIT optimizers and multi-core CPUs. This obviously could be done with an API (perhaps an internal DSL) for a collections library in Java, but the appeal of this solution was that the researcher could simply write a closure and the DSL would take care of the rest. Since C++ also supports operator overloading, the CPU and L2 Cache optimizations could also be exploited easily in that language, altough most of the published work in that space still involves iterating through the contents of a collection and evaluating the entire expression repeatedly, rather than allowing an expression to combine scalar values with numeric collections.

The code is available at GIT Hub under the Groovy Numerics Repository ZIP: TAR:

Groovy Finance

2009-05-27T16:01:00.000-04:00

Presentation from GR8 Conference in Copenhagen, Denmark:

Overview of Performance and Scalability Issues for Groovy-based DSL technology for Quantitive Finance Applications:

Presentation at Goggle Docs

Groovy Finance at Slide Share

Flattering summary of the talk here Getting Groovy Review