substructural: Programming and the Markets

Permanent Portfolio

2012-03-02T06:00:00.000-08:00

Amidst the past few years of turmoil, Harry Browne's Permanent Portfolio is an interesting case. Browne is an investment manager, author, and two-time Libertarian Presidential candidates (for some reason a whole lot of investment managers are Libertarian). The Permanent Portfolio is composed of four equally weighted components: stocks, bonds (long-dated Treasuries), cash (short-term Treasuries), and gold (bullion). The Permanent Portfolio is currently available to the public in two forms: Michael J. Cuggino's Permanent Portfolio mutual fund (PRPFX) and Global X's Permanent ETF (PERM). Of course, one can certainly build one's own permanent portfolio using individual securities and ETFs. As least from PRPFX's perspective, the lost decade was hardly a lost decade. It returned a respectable 164% for the period 2002-2011. That isn't to say that there wasn't some volatility along the way. During the depths of the crisis from June 2008 to February 2009, the portfolio experienced the maximum drawdown of 19.6% (though max quarterly loss was only 6.86%). Cuggino's execution emphasized Swiss sovereigns (in Swiss francs so there is some currency exposure) alongside US Treasuries. For the growth component, he overweights energy, miners, and REITs.

Bid-Ask Spread

2012-03-01T06:00:00.000-08:00

One reason for preferring highly liquid versus illiquid products is the bid-ask spread. This is a cost built into a trade when the trade is a market order. This spread also happens to be the market maker's profit for providing liquidity, whether it be a traditional specialist or a high-frequency trader taking the other side of your trade. Though I usually trade using limit orders to cut down on the spread I pay, for illiquid issues, it is really difficult to get the spread down by much if I want any timely execution.

One case I stumbled on is that of specialized ETFs. With so many specialized ETFs on the market, slicing, dicing, and grafting all different kinds of securities, some of them are bound to be too exotic to gain the trading volume of a typical S&P 500 stock. A case in point are the ETFs issued by brokers specifically for their own customers. Whereas SPDRS, Vanguard, and iShares ETFs trade millions of shares a day, some of these broker-tied ETFs only trade tens of thousands. These ETFs can be traded by anybody via any broker, but the customers of the issuing broker receive incentives such as commission-free trading. The price, however, is greatly reduced liquidity and large bid-ask spreads. I frequently see spreads of 0.5%+ for some of these products. For a large number of trades and a good amount (> $2000), paying the spread quickly becomes more expensive than paying a hefty commission. Large bid-ask spreads certainly aren't restricted to certain low volume equity-like products. Spreads in forex are quite lucrative for forex brokers, some of whom do not charge commission at all in favor of profiting for spreads. For currency-pairs such as the New Zealand Dollar (NZD), large spreads are quite common. In contrast, EUR-USD and JPY-USD usually maintain 1-2 pip spreads. However, during major events and announcements, even these high-volume instruments may see spreads widen considerably.

Market Manipulation, Part 1

2012-02-28T06:00:00.000-08:00

If the investment advice and forums are any indication, a lot of people consider the markets rigged and manipulated. But what is a good working definition of manipulation? There is price manipulation. That entails the defining what an "artificial" price is. Price manipulation is probably one of those things with a long, long history. One of the most famous cases is that of the Hunt brothers' attempted cornering of the silver market in the late 1970s and early 1980s. Market bubbles may also contribute to "artificial" prices, but bubbles are more of a natural psychological reaction of market participants, not some insidious conspiracy. This difficulty works both ways. Government and industry regulatory organizations cannot be too specific about what signals of fraudulent market activity they are scanning for lest the perpetrators simply work around those signals to escape detection. Besides straight price manipulation, regulatory agencies also consider order flow and spread manipulation.

Johan and Cumming did a study on Market Surveillance regimes around the world in a 2008 paper Global Market Surveillance.

Rosa Abrantes-Metz has written a number of papers on the subject including a 2007 paper Is the Market Being Fooled? An Error-Based Screen for Manipulation.

Flash Crash Research, Part 1

2012-02-15T06:00:00.000-08:00

Unsurprisingly, given the interest of regulators and trading firms, there is a growing literature on the May 6, 2010 Flash Crash and "mini-flash crashes" throughout recent history. Unofficial high-speed liquidity providers, free from any contractual obligations, can become high-speed liquidity takers. Filimonov and Sornette investigate prediction of endogenous-feedback loops in the research paper Quantifying reflexivity in financial markets: towards a prediction of flash crashes.

Behavioral Finance and Sentiment/Tone Mining

2012-02-14T06:00:00.000-08:00

There are two prominent claims about the stock market: one is that machines are driving the entire market these days. The other is that behavioral finance works and even sentiment-based trading can produce excess profits.

Dividends and Capital Gains Taxes

2012-02-10T06:00:00.000-08:00

It probably won't garner much fanfare this time through, but the Bush-era (Jobs and Growth Tax Relief Reconciliation Act of 2003) qualified dividend and long-term capital gains tax cuts are set to expire by the end of 2012. This would potentially more than double the tax on qualified dividends. For non-tax sheltered accounts, this could dramatically affect the net returns of dividend income-oriented portfolios especially if there ends up to be a discrepancy between qualified dividend and capital gains taxes. It will be interesting to see how this affects investment strategies. Tax-free muni-bonds have appreciated considerably during last year. The relative tax efficiency of different investment instruments may change in the decline of special treatment of qualified dividends and long-term capital gains.

Richard Shaw studied this issue a few years ago before Obama and Congress extended the tax cuts.

Functional Languages and Call-By-Value, Part 1

2012-02-09T06:00:00.000-08:00

A whole lot of work goes into avoiding unnecessary copies in C++. Much of this responsibility lies in the programmer with manual optimizations such as passing large objects by pointer or by reference rather than by value. This concern is pervasive in the language, from the choice of increment/decrement operators to the implementation of constructors. Many compiler optimizations are also target copying such as the return value optimization (RVO) and, more recently, the move semantics in C++11. The reasoning behind the emphasis on copying seems intuitive enough: pass-by-value of any data larger than a primitive type (i.e., larger than a pointer) gets too expensive especially if the data in question is in a temporary which must be destroyed anyway. C++'s machinery to work-around this inefficiency isn't representative of imperative and object-oriented languages. For example, Java makes references the default way for manipulating objects even though the primitive calling semantics is pass-by-value. However, in functional programming, copying is seldom the overriding emphasis. Why isn't copy as big of a deal in functional languages? For the sake of argument, I will take ML as the canonical functional language. Lazy evaluation in languages such as Haskell adds another layer of complexity which I won't address here.

Indicators and Timeframes

2012-02-08T06:00:00.000-08:00

MarketSci has a short post on what they consider long, intermediate, and short term indicators and strategies. Most indicators can vary sampling periods in order to smooth them out to avoid false alarms. As indicated by MarketSci, the relevancy of different indicators does depend on the amount of data as well as the timeframe. However, with the advent of practical high-frequency data, it is no longer the case that smaller time frames necessarily implies sparser data. One could certainly be sampling weekly for a multi-year indicator and end up with less data than sampling ticks for a few minutes in high-frequency data. The guidelines seem to be that long-term is ruled by trend-following (e.g., moving averages), intermediate-term by mean reversion, and short-term by "noise" (their example is RSI).

Quantitative Behavioral Finance

2012-02-06T06:00:00.000-08:00

Though Fama's Efficient Market Hypothesis (EMH) and variants thereof reigned unchallenged for several decades, during the 1980s and 1990s, behavioral finance gained significant credibility. Behavioral finance has since evolved and given rise to subfields such as Quantitative Behavioral Finance. The hypothesis remains the same: markets are not completely efficient because the human participants are not completely rational. Cognitive biases are the main culprit. Quantitative Behavioral Finance takes this idea a little further by rigorously modeling market prices given such biases (which manifest themselves in terms of underreaction and overreaction) exist by combining differential equations and statistical time series analysis.

Richard Thaler's article, "The End of Behavioral Finance", is an excellent survey of the first decade.

Saving Up for College Tuition and Hedging, Part 4

2012-02-03T06:00:00.000-08:00

Are prepaid tuition programs a great investment? One is right to be skeptical. The programs vary considerably from state to state. Bankrate.com has an article about some of the programs. It turns out that one can be paying anything from 41% to a slight discount to current tuition. Two states, Pennsylvania and Texas offer programs which do not ask for a premium as long as you use the tuition vouchers for state schools. In the Texas case, you receive fund performance if you elect to go to a non-state school. Virginia's program appears to be offering tomorrow's tuition at a slight discount even compared to today's tuition rates if one goes to the most expensive state school. Otherwise, you would be paying a premium. For most of the state programs, tuition inflation will have to accelerate considerably for the programs to be worthwhile. Still, though purchasers of prepaid tuition vouchers pay a premium, the states are still on the hook if tuition inflation does get out of hand.

Saving Up for College Tuition and Hedging, Part 3

2012-02-02T06:00:00.000-08:00

Ever since the government permitted it, many private colleges have been hopping onto the tuition prepayment plan bandwagon. Unlike the College Board's IC 500 index, tuition prepayment often does not include room and board increases. Colleges including some of the Ivies (e.g., Dartmouth, Penn, Princeton), MIT, Stanford, UChicago, and USC tout the private college prepaid plan. For a complete list of the 270+ private schools using this plan, see the consortium's website (managed by OppenheimerFunds, which also happens to manage many of the state 529 plans). States sponsor their own, but some are portable and can be used to fund tuition at out-of-state private schools or even select foreign ones.

Saving Up for College Tuition and Hedging, Part 2

2012-02-01T06:00:00.000-08:00

To answer the question of college tuition hedging, we need to determine the amount of tuition increases and the variability in that change. Generally, higher education revenues come from federal and state aid, alumni giving, endowment returns, and tuition. For research universities, a big chunk comes from research grants. Thus, changes in funding levels for each of these components must be compensated by the others. How have these factors evolved in the past few decades? Can we explain tuition inflation in terms of these other factors?

This is second in my on-going series of posts on college tuition and investment. See the first post.

C++11 Compiler Support

2012-01-31T06:00:00.000-08:00

Compiler support for C++11 is quite uneven at this point. Both Visual C++ and the Intel compiler only support 31 of the features. GCC has significantly better support at this point (48 features).

Trade Frequencies, Part 2

2012-01-30T06:00:00.000-08:00

One of the main challenges in high-frequency finance is the irregular arrival of prices. Once you get down to the tick by tick prices, you can't count on normal interval time series. There are autoregressive models which support irregular arrival of prices. Engle and Russell's autoregressive conditional duration (ACD) model comes to mind (described in Econometric Modeling of Multivariate Irregularly-Spaced High-Frequency Data which extends the Engle-Russell Autoregressive Conditional Duration (ACD) model for the multivariate case).

Stock Price Limits and ADRs

2012-01-27T06:00:00.000-08:00

Some foreign stock markets have daily price limits. For example, in Taiwan, the daily price limit is 7%. How often do we hit these limits? The US ADR for Taiwan Semiconductor (TSM) exceeded the daily price limit ceiling 114 times and dropped below the daily price floor 47 times during a 3597 trading day period from 1997 to yesterday (using Yahoo's adjusted prices). There turns out to be a few papers on price limits and international markets.

Finance Research Papers

2012-01-26T06:00:00.001-08:00

Here are some papers of interest I ran into recently:

Academic Programming Languages in Mainstream Use

2012-01-26T06:00:00.000-08:00

It is said that once a programming language is born, it never really dies. That may be so, but popularity can still be a fickle thing. I think it is safe to say that most academic programming languages never make it out of the lab in a serious way. However, there are a few prominent exceptions to this observation, some of which were and are wildly successful:

Finance Research Papers

2012-01-25T06:00:00.000-08:00

Here are a few hot-off-the-press research abstracts which caught my eye:

Need for Speed: An Empirical Analysis of Hard and Soft Information in a High Frequency World studies news sentiment-based high-frequency trading using an extension of Hasbrouck's market microstructure model (and Chaboud and Tookes) and NASDAQ high-frequency data from 2008 to 2009. The paper seeks to answer whether we can effectively do machine-driven trading based on news sentiment and whether speed matters. The author distinguishes between "hard" and "soft" information events where hard events are price data and soft events news ticker items, blog posts, and Twitter messages (though this paper focuses on news ticker alone). This study only uses Reuters News Sentiment software. The conclusion is that at this point, non-high frequency traders have an advantage in processing the "soft" information events. I think this area is gaining quite a bit of attention with both bigger firms (Thomas Reuters, Dow Jones) and smaller ones (a startup named Stockr.com (invite link) for example) are investing in news sentiment and social media-based trading (respectively).
Market Making Under the Proposed Volcker Rule
No Strings Attached: When Giving it Away Versus Making Them Pay Leads to Negative Net Benefit Perceptions in Online Exchanges

New C++ Features and C++ Texts

2012-01-24T06:00:00.000-08:00

Without pretty fundamental changes such as concepts, it will only be a matter of time before we get a smattering of books on C++11. Some existing C++ books have been updated with a chapter to two on C++11 features. They will of course vary in quality considerably. David Vandevoorde is behind at least a couple of the new features. He has a book C++ Templates: The Complete Guide on template metaprogramming.

Writer's Market

2012-01-24T05:54:00.000-08:00

A couple of days ago, I encounter 2012 Writer's Market Deluxe Edition (Writer's Market Online) at a neighborhood bookstore. The book contained a catalog of freelancing opportunities in a wide assortment of magazines and journals. What I found interesting was that financial and technology freelancers did not receive an appreciably higher rate than other areas. There were certainly exceptions, but for the most part, there was no real discrepancy between rates in different fields. The main trading-oriented publication the book listed was www.traders.com (Technical Analysis, Inc., publisher of Stock and Commodities, Working Money, and Traders.com Advantage magazines), where freelancers apparently contribute a good deal of the articles.

According to the Editorial Guidelines, the top 5 hot topics are relative strength indicator (RSI), average directional movement rating (ADXR), Fibonacci ratios, MACD and moving averages, and volume trends. I am a bit surprised to see RSI so prominent. In contrast, stochastics and chart reading are much further down on the list.

Saving Up for College Tuition and Hedging, Part 1

2012-01-23T06:00:00.000-08:00

One of the biggest expenses for many American families is college tuition. In fact, it is a component of the Consumer Price Index (CPI), though not a very big component. The other overwhelming expenses are transportation (typically cars) and housing. For transportation and housing costs, you can at least partially hedge against further price increases (however imperfectly) by investing in appropriate securities (crude or RBOB futures and Case-Schiller housing futures). According to the December 2011 CPI report, tuition has increased by almost 7-fold since 1984 (the baseline of the CPI). For comparison, tuition increases have dwarfed even growth in hospital services expenses (only 6.5x). The only component of the CPI that grew more was tobacco (8.4x). Thus, not only is tuition a big expense, it is also one of the fastest growing. According to the Bureau of Labor Statistics (BLS)'s analysis, the college tuition inflation rate averages about 6.7% annually for the past 10 years (with a low of 4% and a high of 9.8%), even amidst recession. Recession exacerbated the increases as governments cut funding. Now what kind of investment can give an 8% annual return even in the midst of a massive downturn? A tax-sheltered education savings account such as a Coverdell or 529 Plan helps, but even then a steady 8% pre-tax return from index or mutual fund investing is quite challenging. MyMoneyBlog puts everything in perspective, showing that tuition increases dwarf that of the housing bubble.

In this series of posts, I will be looking into the cause of tuition inflation and the different possibilities for dealing with the phenomenon in investment terms.

C++ and GCC

2012-01-20T06:52:00.000-08:00

Now that C++11 has been live for a little while, I was curious of the state of support from the major compilers. GCC/G++ is the major one. As of GCC 4.7, it appears to support of good deal of C++11 features which actually made it into the standard (concepts being the big omission). Variadic templates, auto-type declarations, initializer lists (vector<int> v {1,2,3}; works), unions supporting all non-reference member types, strongly-typed enums and many others made it into GCC. There is even a range for (for i : collection), something Java incorporated a while ago and the scripting languages had before then. The omissions (stuff in the standard but not in GCC 4.7) include garbage collection and most of the concurrency features.

Algorithmic Finance

2012-01-19T06:00:00.001-08:00

There is a brand new journal combining Computer Science and Finance, Journal of Algorithmic Finance. Both the advisory board and editorial team are ensemble casts with some of the biggest names in computer science and finance. They just published their inaugural issue in December 2011. The top paper (as indicated by number of SSRN downloads) is one on Markets are Efficient if and Only if P = NP, which perhaps is very reassuring to all the traders out there, at least at a theoretical level. For those unfamiliar with the terminology, P means solvable in polynomial time (i.e., we have reasonably smart, efficient algorithms to solve them) and NP means verifiable in polynomial time (i.e., given a solution, we can verify that it works efficiently). NP-complete is a class of problems such that all problems in NP can be (efficiently) reframed in terms of any NP-complete problem. For problems in NP but not in P, we generally do not have efficient algorithms for exact solutions. Instead, we pretty much have to fall back on exhaustive search (i.e., try all the possible answers and see what works). If one can solve an NP-complete problem efficiently in the general case, then one can solve any problem in NP efficiently, which potentially saves some astounding sum of money and enables a lot of previously impractical technologies. The more interesting implication of the paper is that the market can serve as an oracle to solve NP-complete problems. Recently DARPA has decided to invest in crowd-sourcing and gamification to solve difficult formal verification problems. Instead of potentially awkward game embeddings of difficult computational problems, I wonder if market strategies may be more effective and direct.

Earnings versus Dividend Yields

2012-01-19T06:00:00.000-08:00

Given the good Bank of America earnings announcement today, I though it is fitting to look at the earnings yield versus dividend yield of the S&P over a 50 year stretch of time. The ratio has been growing for a long, long while. Back in the 1960s, companies paid out a lot more of their earnings in dividends. Even given the rising trend, the ratio seems over-extended at this point. We have pretty high earnings yield at 7.7% but only a 2.1% dividend yield. The ratio seems to fall whenever we have some recession or slowdown, indicating that dividend cuts may lag earning declines. Assuming that earnings yield at least hold the line (a big IF), the long term trend suggests an overall dividend yield of 2.57%.

Net Worth, Income, and Media

2012-01-18T21:00:00.000-08:00

In New York, everywhere you look is CNBC and Bloomberg. Both tout how their viewership has high net worth and income. With all the captive audiences on trading floors around the world, that isn't a far-fetched claim. For the most part, though, all I ever see on those two channels were GEICO commercials. The interesting part is that as a percentage of viewership, seekingalpha.com does better than both CNBC and Bloomberg at attracting people with household incomes 100k+ (44% versus 40% and 38% respectively). One can do better than that if you can convince kitcometals.com, Neiman-Marcus, or ThinkOrSwim.com to let you advertise on their sites which attract 56%, 41%, and 52% respectively of 100k+ household income viewership as a percentage of total viewership.

I would have included MoneyScience.com in this comparison but the data source I used was quite US-centric.

Microstructure Modeling

2012-01-18T06:00:00.000-08:00

Jonathan Kinlay has an interesting list of papers on market microstructure including his synopsis of each. Many of them applied a vector autoregression model to quote and trade data. The focus, however, is always the impact of the limit order book and the strategies for generating new bids and asks on the limit order book. All of the studies focused on the stock markets. Perhaps the most interesting of the papers is a recent one on Price Dynamics in a Markovian Limit Order Market from Rama Cont of Columbia, which provides a mostly analytical model for high frequency dynamics of prices and order flow with endogenous relationship between durations and price changes. Most of the data in this study came from 2008. According to that data, for certain DJ stocks, ~1.2% of observed bid-ask spreads were more than 1 tick, thus not as pertinent to the model. The average lifetime of such a spread appears to be only a couple of milliseconds. The model does consider order flow in the presence of market orders and cancellations, including the case when they dominate limit orders.

I also found a number of books on the subject (more after the jump).

Memory Management and Concurrency in C++

2012-01-17T06:00:00.000-08:00

Despite the flurry of activity from the Boost and C++11 standards committee, two crucial things remain quite challenging: efficient memory management and concurrency. What started me down this train of thought was some good old code reading. I encountered plain old vectors of pointers. There are apparently a handful of alternatives to this. Boost implements ptr_vector that keeps track of the lifetimes of all its elements as a unit. vector<shared_ptr> is another possibility. The core of the problem is that since vectors' underlying representation is a pointer, and one cannot get a pointer to a reference (the assumption being one wanted the efficiency of reference-passing but with the convenience of STL containers).

More after the jump

Airport Reading

2012-01-16T21:00:00.000-08:00

When I am stuck in the airport I often visit the bookstores there. Airports are apparently one of the last bastions where bookstores still exist whereas they have completely disappeared in some towns. Most of the time, airport bookstores do not carry anything of interest to me except the latest Barron's and a few finance magazines. Consequently, I was surprised pleasantly to see at least two of Michael Lewis' books at one airport bookstore, Boomerang: Travels in the New Third World (about the roots of financial crises in Greece, Ireland, Germany, and the US) and Moneyball (about the business and economics of baseball), both being NY Times bestsellers. Lewis the the author of Liar's Poker, a sardonic expose on the unreal bigger-than-life world of Wall Street in the 1980s.

Earnings season is upon us

2012-01-10T09:48:00.000-08:00

It's earnings season again. Alcoa started us on a sour note with a multi-cent miss even after excluding one-time items. Tiffany's warned. But benign retail numbers were out this morning (with Ross and Costco among others doing fairly well). This has given the market a lift.

I revisit a trade I was watching but did not make after the jump.

Trade Frequencies, Part 1

2012-01-06T07:00:00.000-08:00

Typically what people refer to as high-frequency trading occurs on the stock markets. However, firms have also branched out to a whole assortment of other markets in attempt to reap the alpha from high-frequency strategies. Moreover, data such as futures prices sometimes serve as a signal for equity trading. Different kinds of markets, however, have considerably different characteristics. Moreover, the volume and trade frequency varies among each individual security. On one side, you have the SPY ETF which is easily among the most actively traded securities in the stock market with daily volumes in the hundreds of millions. During August 2011, SPY's volume even spiked to as much as 717 million, though 100-200 million is more typical. To put that into perspective, the total daily volume of the NYSE is about a couple billion in recent times. In contrast, some securities are barely traded at all.

Garbage Collection and C++

2012-01-05T11:01:00.000-08:00

C/C++ had the potential for automatic garbage collection in the form of the conservative mark-sweep Boehm-Demers-Weiser garbage collector for decades (at least from 1988 onwards). Although an early version of the garbage collector is even included in the GCC distribution, only a few groups actively use it. Some have used it as a leak detector. Boehm himself explains this as due to lack of standardization. With C++11, the hope is that this will change with official sanctioning of garbage collected implementations. The slide presentation you can find in the above link summarizes the design. The argument for garbage collection in C++ is the move to multicore, where the claim is that GC parallelizes better than manual management and that some parallelization techniques are simplified in the presence of GC.

POPL 2012 Papers

2012-01-05T10:15:00.000-08:00

It's just a few weeks until POPL 2012 (Symposium on Principles of Programming Languages, one of the top programming language theory research conferences) in Philadelphia. The program has been out for a while. This time, there are three papers on C/C++ semantics. Apparently we have gotten to the point where researchers have (mechanically) formalized interesting chunks of that large, complicated edifice. The one coming out from INRIA [PDF] has a mechanized (Coq) semantics for C++ construction and destruction including C++11 features. The authors actually give a formal proof of the RAII (resource acquisition is initialization) pattern, specifically that in a terminating program every construction of a subobject is indeed matched by a destruction. The process of developing a formal semantics also helped identify issues in the C++ standard both C++03 and C++11. On the type systems side, there is also a paper from Adobe Research on gradual type systems, especially a type inference scheme with support for dynamic types. One paper describes a type system and language design supporting probability density functions for custom probability distributions and continuous probability. Apparently probability distributions are monads too!

Market Indexing

2012-01-04T10:01:00.000-08:00

Fundamental indexing, an idea promulgated by Rob Arnott and his firm, caused quite a stir when it was introduced in 2004 with many questioning the whole idea. It has since given rise to a number of ETFs. The original is PRF, an ETF launched in December 2005. According to PowerShares' site, they are benchmarking PRF against the Russell 1000. Powershares followed on this product with 5 more, covering the developed markets ex-US (PXF), Asia Pacific ex-Japan (PAF), emerging markets (PXH), developed ex-US small cap (PDN), and US small-mid cap (PRFZ).

Forward Looking

2012-01-03T11:22:00.000-08:00

Now that the holidays are over, what is going on in the markets? A couple of European debt auctions went fairly well last week. This does not change the overall long-term picture, but looks like nothing collapsed over the holidays. Moreover, the Iran-Strait of Hormuz situation could have spun out of control early on, but it did not (yet).

I was curious what news items were affecting the companies on my equity watch lists (both long and short). On the growth side of things, the basic materials and energy side lead the market (APA, EOG, ROSE, APC, HAL, NE, MOS, FCX). FCX is up ~6%. The rest are up more than 2% for the most part. HAL is suffering from some headline shock due to its spate with BP (BP is asking HAL to foot the cleanup bill plus lost profits), but the damage is mild since nothing is decided yet.

Shareholder Meetings

2011-12-22T09:59:00.001-08:00

Matthew Rafat's blog willworkforjustice.blogspot.com has a first-hand record of shareholder meetings for a number of companies, though mostly in the Bay Area since that is where he is based. With organizations such as moxyvote starting up and various motions towards more responsive corporate governance, this record is an interesting data point. Large shareholders (pension funds, etc.) are still for the most part slumbering giants.

How long does it take to compile a web browser, Part 1

2011-12-20T06:00:00.001-08:00

In today's brave new world, people can build and deploy a web app very quickly. However, on the other side of the equation, systems software such as web browsers are not getting any simpler. The cost of the rich media experience in modern web apps quite frequently borne by systems software including browsers, servers, and plugins. Just eyeballing, in Chrome (default multi-process mode), each tab take 30-100 MB of RAM. Luckily, I am not one to keep many tabs open concurrently, but many, many people do. A rich web experience can quickly gobble up whatever amount of memory you can throw at it. There are many people who have compared memory usage for Chrome, Firefox, Safari, and Internet Explorer (TechPP, CNet, Tom's Hardware, DotNetPerls, and many more I am sure), but, here, I would like to take a look at another facet of web browser complexity: source code size, time to build, and size of debug executable. This post follows and expands upon the type of study I did on open source finance software.

US Debt Service

2011-12-20T06:00:00.000-08:00

The economic times have really changed. The scope of household deleveraging is quite astounding. The Federal Reserve releases a figure called the Financial Service Ratio which measures amount of consumer and mortgage debt servicing including automobile lease payments, rental payments on tenant-occupied property, homeowners' insurance, and property tax payments to disposable personal income. For renters, the ratio peaked around 2001 at 31.05. For homeowners, it peak a lot later around 2007 at 17.55. Both have been sliding ever since. This data refers to the country as a whole. The picture for the individual regions may look different.

Symmetric Type Sharing in ML

2011-12-19T10:30:00.000-08:00

In the Standard ML language, there are two primary mechanisms for refining a module signature after the fact. One is a symmetric mechanism called type sharing and the other called where type, aka fibration. These are useful for facilitating modular programming by enabling reuse of module signatures (i.e., the syntactic "type" of a module).

Buybacks and Dividend Growth

2011-12-16T13:51:00.000-08:00

There is a lively discussion on one of the front-page stories on Seekingalpha about whether Buybacks destroy value. As in my previous posts, I am on the fence regarding this one. It really varies on a case to case basis depending on where the money is coming from (some buybacks are highly leveraged and some special dividends come from debt issuance) and where it could have gone instead. It was surprising to see at least one investigation seemingly indicating that Buyback Achievers trump Dividend Achievers by a considerable margin. In terms of the intersection between PKW and PFM, it is only 12 companies: IBM, TGT, WAG, CB, FDO, WMT, GWW, CTAS, TJX, SFG, CASY, LOW. This group outperformed both PKW and PFM over a 1 year time frame.

Social Web IPOs

2011-12-16T10:46:00.000-08:00

Looks like Zynga's IPO day didn't start a social web frenzy (down 7.8% as of now). The broad market certainly was no help here. Quite a pattern is forming with Pandora, Groupon, Linkedin, and Renren. None of these led to an unqualified success, and most of them are doing quite poorly especially if one bought at the open of the first day. Those who bought at the IPO price did considerably better for each of those 3 names. Groupon and Pandora debuted last month and in June respectively. Linkedin and Renren debuted in May.

Can free tiers be tear free?

2011-12-15T07:00:00.000-08:00

Many of the cloud computing services offer some kind of free tier these days. Most of them are time-limited (e.g., Amazon's free tier lasts for 1 year, Microsoft's 90 days), but some are not including Google. How do they stack up?

Data-Driven Language Design

2011-12-14T15:25:00.000-08:00

One recurring issue with the evolution of programming languages is the tension between feature creep and stagnation. Some programming languages manage to evolve very rapidly, incorporating all kinds of features in response to developer requests or the language architect's leading. Brian Goetz has an interesting article on DeveloperWorks which argues for using "corpus analysis", studying the actual frequency of use of language constructs in the corpus of source code, to guide the evolution of a language. In his article, he describes two examples, precise exceptions rethrow semantics and type inference, where corpus analysis played a role in determine how Java evolved. When I was working on SML/NJ, we informally used this technique to determine the best design in terms of certain type checking/inference and module system elements.

Share Buybacks, Part 4

2011-12-13T13:57:00.000-08:00

Taking a sampling of the 41 PKW Buyback Achievers I could find XBRL annual reports on, there are a number of interesting points. The mean buyback rate for 2010 was 7.3% of common stock shares outstanding (DEI). Given this data point, IBM's rate of buyback seems only a middling one. I would caution generalization from a single year's worth of data, but it does provide a little perspective. A particular high or low buyback rate does not mean much by itself. One has to consider where the money for the buybacks is coming from and how is the rest of the business doing.

Vicious Cycle

2011-12-13T12:35:00.000-08:00

The Fed didn't ride in with the cavalry today. Looking from their perspective, why would they? The domestic data from the past few weeks did not indicate catastrophe. Popular support for further easing is tenuous at best. The main risk is from the debt situation in Europe. The evanescent hope that fueled the past few weeks' action dissipated just as quickly. The Dollar and Treasuries skyrocketed from the lows of the day. In Europe, there is a vicious cycle going on. The large private holders of sovereigns (i.e., banks and funds) insist on being made whole, thus pressuring the very sovereigns they don't want to default. The European governments insist on more and more austerity, negating what little chance they had to have secular growth lift them out of the mess.

Server Infrastructure, Part 2

2011-12-13T12:03:00.000-08:00

Following post on Oscigen's benchmark, I was curious how much does increased memory usage due to Ruby and Python-based web app stacks affect the bottom line. Plotting Amazon EC2 instance cost against instance memory shows that costs scale roughly linearly with the memory allowance. The least squares fit is y(x) = 0.028*x + 0.079. Linear scaling means that when Ruby/Rails take 10x the memory (roughly the difference between OCaml/Oscigen and Ruby/Rails) then it costs 10x as much in the long run (and after scaling up). For smaller instances, the difference is probably less. Of course, this doesn't take into account the productivity difference. However, although Ruby and Rails are clearly more productive than C/CGI, it is not clear that it is more productive than other high-level languages with better memory use and performance characteristics.

A Paper on "High Frequency" Treasuries

2011-12-12T11:00:00.000-08:00

There is a paper from London Business School dated from a while back (2002) that studies simple pairs strategies applied to the whole universe of US treasuries secondary market. The data used are intraday quotes and transaction information from GovPX (thus "high frequency"), which has since been acquired. The paper has an interesting table comparing equity and treasury markets (Table 1). One particular metric is the "social acceptance" of shorting the securities. The claim is that shorting equities has low acceptance whereas shorting treasuries is "less affected". The proposed strategies reduced the standard deviation of returns considerably though the level of returns were also dragged down somewhat. The best performing strategies generally kept risk controls very tight. When transaction and financing costs are accounted for, the returns start to trail the risk free return, though it outperforms equity and the treasury bond index in terms of Sharpe ratio and Gain-Loss ratio. Curiously, these strategies are slightly positively correlated with equities and slightly negatively correlated with the bond index.

Save bits, save power, save the world, Part 2

2011-12-10T21:17:00.001-08:00

The GHC Haskell and OCaml compilers do not have builtin popcount support, so again I precomputed the bit pop count for each ASCII letter. Using the same ~9 Mb 4x concatenation of /usr/share/dict/words from last time I measured the performance of the resultant code. This time, the test machine was a Macbook Pro 2.16 GHz with 2 Gb of RAM. The microprocessor is a Core Duo T7400 which has no support for the popcnt instruction anyway.

Europe Again

2011-12-08T15:07:00.001-08:00

The markets closed on down note. After hours, we have ES, ZN, and DX at 1231.75 (down ~2.5%), 131'055 (up ~0.39%), and 78.920 (up ~0.55%) respectively. Tomorrow is the end of another summit (an EU summit). Europe remains the mover of markets for now.

Risk Aversion

2011-12-08T06:58:00.001-08:00

The Dollar is up, 78.780 (+0.310). Treasuries are holding quite firm at 130'240. The ECB lowered rates back to the record low to 1.00%, offered banks unlimited cash, but did not initiate new bond purchases. Gold has tripped up a bit, but nothing game-changing at this point. Taking a look at the weekly for large-cap equities (S&P 500 E-mini), one can see the slow but steady upward Europe hope rally (rising channel). Today's action appears to have rejected new highs, but there has been no significant confirmation of a break in this very short-term time frame.

In terms of the individual stocks front, I will be looking at some emerging market issues. Brazilian metals miner VALE looks to be hanging around the 52-week bottom at 22.42. Brazilian oil giant Petrobras PBR bounced up a little but lagged the broader market. Today it took a 3.84% plunge to 27.10. Chinese oil offshore driller CNOOC CEO is at 193.68, which is actually around the top of its recent range. It currently yields around 2.9%

Save bits, save power, save the world, Part 1

2011-12-07T07:30:00.001-08:00

Ok, the title was a little tongue-in-cheek. I did a fairly whimsical experiment yesterday. Since text strings are represented as bits which are either 1 (on) or 0 (off), I was wondering which unused domain names used the minimum number of "on" bits. The answer may be non-intuitive to the non-computer scientist.

Substructural Type Systems and Performance, Part 1

2011-12-07T06:20:00.000-08:00

Why is the name of this blog "substructural"? In turns out that in the realm of advanced type systems, there is a family of type systems derived from a family of logical systems called substructural logics. The chief distinction of substructural type systems is that one or more of the "structural properties" of type environments are eliminated. These rules are exchange, weakening, and contraction. Exchange allows arbitrarily reordering bindings in the type environment. Weakening enables adding new bindings. A type derivation is deemed "weakened" in the sense that if a program already typechecks using a certain type environment, adding new bindings to that environment won't negate the well-typing of the program.

The Steam Engine of the 2010s?

2011-12-06T15:27:00.000-08:00

I read a couple of technology-/startup-oriented articles recently. One was yesterday's Forbes article on developeronomics which describes the growing prominence of talented software developers and investment in them in stark terms.

Share Buybacks, Part 3

2011-12-05T11:03:00.001-08:00

Following my previous discussions of share buybacks here and here, let's look into the distribution of the share counts for the PKW (Share Buyback Achievers ETF) components. The components of the Share Buyback Achievers exhibit significant diversity in outstanding shares. For this study, I used the outstanding share information from Yahoo Finance which appears to be a rough undiluted number. The mean, median, and standard deviation of share count are 242M, 81M, and 430M respectively. The component with the minimum number of shares outstanding in this fund is homebuilder NVR with a mere 4.98M shares out. Mega-retailer WMT has the most with 3.44B shares.

Firestorm

2011-12-02T10:40:00.001-08:00

The past few days have seen a veritable firestorm of flames between the Java and Scala communities. The proximate cause was a leaked private email outlining what the Yammer folks disliked about Scala. An official post from Yammer followed but not before many bloggers had a field day with the leaked email. What is interesting is that one such discussion on Stephen Colebourne's blog pointed that the the lack of a "module system" is a principal deficiency of Scala. This point, mind you, was not part of the Yammer email. In fact, it preceded the email by a few days. The post cited the Scala's community's response to an inquiry about Scala and "module systems" [Google Groups]. That inquiry initially resulted in some misunderstanding.

Multiarmed Bandits

2011-12-02T08:11:00.001-08:00

I tweeted a little while ago about a post from the Untyped people on applying a multiarmed bandit algorithm to website optimization (in contrast to A/B testing). It turns out that many have considered the multiarmed bandit problem for optimizing market maker profitability,Bandit Market Maker by Penna and Reid [PDF]. The basic idea is to dynamically optimize (i.e., reinforcement/online learning) the use of k-levers each operating under initially unknown and eventually partly known distributions. Presumably, the more one uses the levers, the more one learns about the reward, but there is an exploration-exploitation dilemma -- since we are operating online one has to choose whether to take the empirically revealed best choice thus far or to continue to explore for more rewarding options. The exploration-exploitation dilemma also matters to genetic algorithms and programming, but the multiarmed bandit problem explicitly optimizes for it. The exciting thing is that after decades of research, they have found optimal algorithms for the multiarmed bandit problem. The Untyped post cites one of them, Finite-time Analysis of the Multiarmed Bandit Problem by Auer et al [PDF].

Crude Oil and Oil Stocks

2011-12-01T11:43:00.001-08:00

One would logically expect oil stocks to track with crude oil prices. For the most part, this is true. Below are the correlation coefficients between a select number of oil services, drillers, refiners, integrated conglomerates, an oil sector ETF (XLE), and an ETF for accessing crude prices (USO), imperfect as it may be due to futures roll. Though most companies track with USO, there are a couple of exceptions. Transocean (RIG) exhibits low correlation with other sector companies and even a negative correlation coefficient with the commodity itself. Halliburton (HAL) has also been exhibiting very low correlation coefficient (0.16). Read more »

Euphoria

2011-11-30T09:03:00.001-08:00

The markets have been alternating quite quickly from euphoria to depression and back to euphoria. Today is one of those euphoric days. S&P e-mini December (ES) is up more than 3.2% as I write this. The 10-year (ZN) took a nose-dive after news from the central banks and ADP numbers (which were very good and came with a hefty upward revision of October numbers), but has recovered to a -0.23% loss. The dollar (DX) has tanked also at 78.450. The next big event is Friday Nonfarm Payrolls (NFP).

Share Buybacks, Part 2

2011-11-29T09:38:00.001-08:00

In my last post on share buybacks, I started by breaking down the components of the Powershares Share Buyback Achievers ETF PKW. The fund PKW sports an average PE of 13, a yield of 0.78%, and a beta of 0.98. Over several periods, PKW outperformed SPY (with a bout of slight underperformance recently):Read more »

Scala Performance

2011-11-29T09:15:00.001-08:00

I just found this experiment pitting several Python-based servers versus a Scala one. After "priming the pump" to get the VM to optimize the Scala one, Scala handled 3.6x more requests per second than the Python Twisted web server. It even handled 8.5% more requests than a largely C-infused Python server Fast Asyncronous Python WSGI Server. No memory use information was given, but these results do definitely tilt towards Scala.

Share Buybacks, Part 1

2011-11-28T11:13:00.001-08:00

I recently read an interesting article on SeekingAlpha about IBM's share buyback record. The article says that over the past 16 years, IBM has been able to half its outstanding share count, which Warren Buffett claims as one reason why he bought $10B worth. That got me thinking, there is at least one ETF focused on share buybacks, PKW PowerShares Buyback Achievers. The fund has 139 components. What is IBM's performance relative to the rest of these? The fund has only been around since 12/2006, but presumably the index (Mergent DRB) has been around a while longer. Some of the components include TGT, DTV, TWX, TJX, COH, AZO, and GPS at 4.77%, 13.4%, 4.99%, 4.82%, 9.11%, 10.62%, and 10.35% decrease in common stock shares outstanding from FY 2010 to FY 2011 respectively. From the SeekingAlpha article, IBM has bought back anywhere from 0.01% to 8.73% of shares in a single year. Stay tuned for more information on the share buyback data point.

This is the first post in a series. The next post is here.

ETF Performance

2011-11-25T09:28:00.001-08:00

Comparing ETF performance is actually somewhat tricky, though the issue isn't particular to ETFs. Though the CFA material has whole sections to deal with presentation of performance, there remains many variables. Returns can be annualized (though generally only performance terms 1 year or more should be annualized) or cumulative. The prices used could be bid-ask midpoints at closing (which is the preferred method by ETF issuers) or last trade price (which is the data available to us mere mortals). The performance can be total return (including any distributions such as dividends and capital distributions) or market price return. The cumulative return could end on today or the last business day of the preceding month. Then there is market and NAV performance. All these factors can make a significant difference in the calculated performance numbers, especially over longer periods. For illiquid issues, the bid-ask midpoints and last trade may differ considerably. Yesterday, I collected cumulative returns for IYY (iShares Dow US Broad Index ETF) from a few places:

Schwab Cumulative

Period	Mkt	NAV
1 mo	11.3	11.3
3 mo	-3.3	-3.2
6 mo	-8.0	-8.0
1 yr	-7.8	-7.8

Yahoo "Trailing Returns"

Period	Mkt	NAV
1 mo	11.30	11.33
3 mo	-3.26	-3.17
1 yr	7.76	7.84

iShares Cumulative

Period	Mkt	Total
1 mo	11.31	11.33
3 mo	-3.15	-3.16
6 mo	-7.96	-7.99
1 yr	7.83	7.87

Though the Schwab and Yahoo data are agreement, notice how the iShares reported performances diverges starting from the 3 mos point. In a low yield environment, the difference between -3.26% and -3.15% cumulative market returns is huge. I have not been able to reconcile this discrepancy exactly. It is not merely the $0.262 dividend distribution during the 3-mo period. I think the moral of the story is threefold:

take nothing for granted
always read the fine print on how performance is calculated
try to obtain performance data from multiple sources

Yahoo Finance Gotcha

2011-11-24T11:22:00.001-08:00

While writing scripts to reproduce the returns information on some ETFs, I found a silly gotcha when using data from Yahoo Finance. It turns out that the website and CSV historical quotes information interprets starting dates differently. If one asks for a starting day that is not a business day, the website will also give quote information for the last business day preceding your starting day. The CSV historical quotes has the opposite behavior. If the starting day is not a business day, the earliest quote that the CSV gives is the first business day after your starting day. For example, the earliest quote http://ichart.finance.yahoo.com/table.csv?s=SCHX&a=06&b=31&c=2011&d=09&e=31&f=2011&g=d&ignore=.csv will give is 2011-08-01 whereas http://finance.yahoo.com/q/hp?s=SCHX&a=06&b=31&c=2011&d=09&e=31&f=2011&g=d will give 2011-07-29, with July 31, 2011 (the month in the URL request is also 0-origin so 06 is July) being a Sunday. This is certainly something to watch out for when fine-tuning data collection from Yahoo.

Pre-Holiday Closing

2011-11-23T16:45:00.001-08:00

The markets close for this short week due to the US holidays. The S&P 500 stands at 1161.79 and the 10-year treasury yield at 1.88. The Treasury market has been telegraphing the massive tail risk for quite a while now ever since February when yields hit 3.74 and have been tanking ever since. Now it looks like the core Euro-zone is feeling the heat with French and even German sovereign yields rising. The German 10-year bund still has a -22.9 basis point spread over the US 10-year, though the 2- and 5-year have 39.2 and 25.2 basis points spreads over their respective US counterparts. On the bright side, Durable Goods did not turn out too bad, but that is little consolation for the volatility wary.

Static Type System and Numerical Computing

2011-11-22T13:23:00.001-08:00

The programming languages with which most people are familiar, such C/C++, Java, Python, JavaScript, and Ruby, presents a very stark contrast. On the one hand, you have statically typed languages (C/C++ and Java) which are amenable to a wide assortment of compile-time optimizations due to the presence of types. On the other, you have dynamically typed languages (Python, JavaScript, and Ruby) which are "fun" to program and amenable to rapid prototype due to more succinct syntax partly due to the absence of explicit type annotations. The sweet spot, in my humble opinion, is statically type but with type inference, a subject of my expertise and doctoral studies. I plan to write a few posts on this subject, near and dear to my heart. Heavy duty Numerical computing is one area where dynamically typed languages such as Matlab, R, and NumPy/Python have gained a considerable mindshare. Since NumPy offloads computations to efficient C libraries, this is quite reasonable. I would like to discuss where I think numerical computing and statistical analysis programs can benefit from a more sophisticated static type system with type inference. To whet your appetite, consider the case that C++'s Boost Library contains the functionality needed to statically check for units (i.e., dimensional analysis). The performance difference between code generated from statically typed languages and from dynamically typed languages is not just the absence of dynamic type checks. Types in static type systems enable a considerable array of optimizations to get rid of that last tiny ounce of latency.

Top 5 Open Source Quant Finance Projects

2011-11-21T07:14:00.001-08:00

In the recent months, I have found the data on open source development projects to be quite fascinating. It turns out that most of the activity in open source quant finance code happens on Sourceforge. I pulled some of that data and charted them.Read more »

Datamining Sentiment from News Text

2011-11-18T10:43:00.001-08:00

In an earlier post, I mentioned different companies using social media to gather information for stock market trades. The larger area of developing predictive analytics and datamining of news article text has several interesting players: Thomas Reuters [PDF], Dow Jones (RavenPack), Predictive Signal, and MarketPsych. Predictive Signal claims 10.4% positive returns (not annualized) over a nearly 3 month period (May to Aug 2011) versus an S&P 500 decline of 9.9%. MarketPsych cites a 25+% better returns than the S&P 500 with a third of the volatility from September 2008 to December 2010. In the latter, they actually traded over that 2 year period using their proprietary signals (MarketPsy Long-Short Fund LP).

Options Expiration Friday

2011-11-18T05:09:00.001-08:00

Today is options expiration Friday and Leading Indicators at 10:00am. Futures currently read as follows:

Contract	Price
ES Dec	1223.00
ZN Dec	130'155
DX Dec	77.840

Correlations

2011-11-17T13:48:00.001-08:00

Looks like the stock market broke down a bit and is hanging outside the previous trading range. I put together a script to calculate correlation coefficients to see where things stand.

	spy	sdy	tlt	zroz	uup	gld	xle	xlf
spy	1.00	0.93	-0.68	-0.64	-0.34	-0.57	0.95	0.94
sdy	0.93	1.00	-0.41	-0.36	-0.15	-0.43	0.83	0.77
tlt	-0.68	-0.41	1.00	1.00	0.69	0.51	-0.77	-0.87
zroz	-0.64	-0.36	1.00	1.00	0.72	0.45	-0.75	-0.84
uup	-0.34	-0.15	0.69	0.72	1.00	-0.08	-0.53	-0.51
gld	-0.57	-0.43	0.51	0.45	-0.08	1.00	-0.42	-0.61
xle	0.95	0.83	-0.77	-0.75	-0.53	-0.42	1.00	0.95
xlf	0.94	0.77	-0.87	-0.84	-0.51	-0.61	0.95	1.00

The correlation coefficients are computed for the past 100-days of returns calculated from adjusted closing prices for each asset. There is a little something for everyone here. Equities (SPY) and dividend-paying equities (SDY) have strong correlations. Despite appreciating crude prices, energy stocks (XLE) are still strongly tied with equities as a whole. To get negative correlation with equities, one may look to treasuries (TLT and ZROZ [Pimco Long Dated Zeros]), the dollar, and gold. TLT and ZROZ similar but in terms of correlations with other assets, it happens to be TLT that exhibits the slightly more pronounced negative correlations despite ZROZ being more of a pure play. Surprisingly, the least correlated assets in this study are gold (GLD) and dollar (UUP).

Programming Language Gotchas

2011-11-16T17:27:00.001-08:00

Looks like I spoke too soon. The October rally was looking a little long in tooth, and a little warning from the credit agencies was enough to get the market to go risk off at least for this afternoon. At least yields did not decline too much (2.01% for the 10-year according to MarketWatch). The Dollar Index (DX), however, has certainly been in an uptrend since the end of October trough.

Coming from the Standard ML world of languages makes me take many things for granted. It also gives me a probably pretty narrow perspective. Hacking on my trading analysis tools in other languages helps me broaden that somewhat, though I have certainly worked in the mainstream languages long before I encountered ML and its brethren. I would like to keep a record of these gotchas as I encounter them. I do not intend this as value judgments but rather a documentation of noteworthy differences from a higher-order typed programming language perspective.

Cash Secured Puts

2011-11-16T10:51:00.001-08:00

Seeing that this morning was a benign CPI day with no earth-moving news from Europe, I thought that it would be an interesting exercise to look at a volatility-selling options strategy. The strategy is a fairly conservative one, cash secured put writing. My sample is the 341 component subset of the S&P 500 with options activity today (i.e., there is are bids and asks). I will be only looking at the nearest to the money strikes to the last traded price of the underlying. The puts expire in less than 3 days (Friday, 11/19/11) so there really is not much time premium left. The returns are computed as put premium (midpoint of the bid and ask) over the strike times the 100 multiplier (i.e., the amount of cash needed in case of assignment). The VIX today (the last time I looked) remains elevated over 30.

The above is a histogram of the cash secured put returns. The horizontal axis marks the returns (put premium/ (100*strike)) and the vertical the number of securities that have that return. The median, mean, and standard deviation for the returns are 0.000675, 0.00101, and 0.00111 respectively. The max is 0.01 for TSS.

Server Infrastructure

2011-11-15T14:45:00.001-08:00

Recently, I have been building a market data feed and order book simulator. Since I had already built an Ncurses front-end (console GUI) for Trader Workstation, this was the opportunity to try out something new. I decided to try out Lift/web, Scala's web framework. Lift/web is a perfectly fine framework. The ORM side of things (Mapper for RDBMS and Record geared more towards NoSQL) still seem to be a work-in-progress (though a very usable work-in-progress), but Comet (Ajax-Push) works as advertised. In my experience, however, memory overhead seems to be a real issue. During development, Lift managed to gobble up all the default heap space after just a few source updates. None of the requests were large by any means. Apparently, there are a few configuration tweaks I still need to try to get this under control, but this whole episode got me thinking: with all the emphasis on massively scalable webapps (it seems everyone aspires to serve millions and billions of requests), why do most people tolerate the memory use profiles of Rails/Ruby, Python/Django, and PHP?

There are probably plenty of issues with this study on Oscigen, an OCaml-based web app framework, but it does seem to reflect the reality that there is a lot of inefficiency in modern web framework stacks. The above benchmark claims that under fairly benign circumstances, Oscigen outperforms Rails by 10x in terms of both requests/sec and reduced memory use (4.5MB versus 49MB). Oscigen's memory profile apparently ties with a simple C-based web app (using FastCGI). Interestingly, on the opposite end of the spectrum, there is also a C++-based web stack, Wt. Regardless of the merits of the benchmark, the fact is that people put up with a considerable amount of memory use. Considering that memory on Amazon EC2 is not exactly free, it does concern me. On one web app hosting organization's site, Micro instances are only good for PHP apps whereas Small instances are needed for the lightest of Rails and Java apps. Large servers with 7.5GB RAM (which currently run from $244/month) are needed for "full-size" Rails and Java apps. Is the current state of things a case of memory and servers are too cheap or caching covers over all problems? There is always the red herring of network latency, but if concurrent requests served with constrained resources is the main metric then memory use matters.

Or maybe it is because good garbage collectors are hard to come by. At least at one point, garbage collection was an issue in Ruby. This chain of thought led me to look up whether there are any good solutions for web stacks with low memory footprints, especially any that come in neat statically-typed packages. There is certainly Oscigen/OCaml. The StackOverflow people have also suggested Adam Chlipala's Ur/Web system. In the latter stack, after some searching through mail list archives, I have learned that Ur/Web uses region memory management (where the boundaries of a request delimits regions). The main website kept mentioning that Ur/Web is fast at least in part due to not having a garbage collector. That, of course, got me curious as to what did it use for memory management. Ur/Web also seems to be built on Standard ML (the Makefile has settings for both SML/NJ and MLton), which is certainly a plus according to my bias. Though explicit regions (aka memory pools [but careful, this is an overloaded term] or arenas) are pretty efficient (being part of Apache, nginx, PostgreSQL), region inference has its own issues, principally that programs written in a region-unfriendly fashion can lead to poor performance. The consensus on the matter appears to be that regions and garbage collection can be combined in a single system to address region-unfriendliness while simultaneously minimizing garbage collection.

Genetic Programming Performance

2011-11-14T15:20:00.001-08:00

There is a whole lot of literature on the subject of genetic and evolutionary algorithms for trading strategies. The quality of the work seems to vary considerably. I have yet to discover the canonical and seminal lines of work in the field. Unlike in programming languages research and perhaps other scientific fields, the bibliographies do not all follow the same chain of citations. Or perhaps they do, but I have yet to discover it. More on this after the jump.

Genetic Programming and Trading Strategies

2011-11-11T13:01:00.000-08:00

From an anecdotal sampling of Linkedin and web discussions, people have applied various machine learning techniques to the creation of trading strategies. The most popular techniques for trading strategies mirror that of the general applied machine learning community, meaning SVM and neural networks are frequently mentioned. One relatively lesser known technique is genetic programming (GP), a variant of genetic algorithms for tree data structures, normally abstract syntax trees. Curiously, the academic community has studied genetic programming quite a lot. Indeed, there are many papers on genetic programming for trade strategies in GECCO (a conference on genetic and evolutionary computation) and other conferences/workshops. Some people from State Street have even contributed their study. The Quant Stack Exchange has a discussion on genetic algorithms where the problem of data snooping is frequently mentioned as a shortcoming, a problem addressed by regularization in conventional learning techniques. I informally survey some of the studies of the effectiveness of GP in a follow-up post.

My cursory interest in this area is the potential impact of programming language design and especially static type systems on the performance of genetic programming for trading strategies. The nice thing about genetic programming is that the results produced can be theoretically unrestricted unlike basic machine learning techniques that make assumptions such as linearity about the underlying model. Practically, however, the results produced by genetic programming are usually small and possibly uninteresting. This is where modern programming languages theory comes in. In the past decade or so, a number of researchers have studied the problem of the generation of random test cases (of which QuickCheck is a prime example). One of the main engineering challenges there is to ensure that the test cases generated do not all fall into a trivial category. The test cases here can range from instances of simple primitive types (e.g., ints) to nontrivial data structures (e.g., syntax trees or data packet queues). Usually it falls to the developer to write functions that generate a good distribution of test cases to ensure, for example, that the probability of getting a list of length greater than 3 is not negligible. In practice, QuickCheck supplies an assortment of combinators that help produce a good distribution. The developer's domain knowledge is still necessary, but the test generation problem reduces down to a choice of combinators.

Semantics of Nested Classes

2011-11-07T09:31:00.000-08:00

Although nested classes are widely adopted in many popular programming languages (e.g., C++, C#, Java, Python, Ruby), I have yet to see a good treatment giving the motivation, use cases, and architectural issues associated with the feature. Moreover, another undocumented aspect is how the semantics of nested classes vary from language to language. They appear to be useful for namespace management (though C++ namespace and Java packages also cover this), simulating closures, and callbacks for GUIs and event handling (basically a variant of closure simulation).
First thing is first, what are nested classes?

class A {
  class B { }
}

In essence, they are scoped type declarations and definitions. Instead of defining a class B at the top-level of the program source, one declares a locally scoped one within the definition of another class, A in this case. One immediate consequence of this is a form of namespace management for user-defined aggregate types (i.e., classes).
There are a lot of gotchas due the language design here. The scoping discipline is incomplete. C/C++'s restriction on shadowing prohibits the following code:

 
class B; 

class A {
  B something;
  class B { };
}

In contrast, the following code compiles:

class A {
  private:
    class B {};
  public:
    B makeB();
}

Despite the fact that A::B is unnameable outside an instance of A, A exports the member function makeB which yields a value of type A::B. Though one cannot name the return value of makeB outside of A, the value can still be used as is in the case in the following:

class A {
  private:
    class B { 
      int x;
       public: 
      B add(B _x) { x += _x; }
    };
  public:
    B makeB();
};

int f() {
  A a0, a1;
  a0.makeB().add(a1.makeB());
}

The above illustrates an important point. C++ nested classes do not declare distinct types for each instance. Although one cannot annotate them as static, they are exactly that. In the example, a0.B and a1.B are of the same type. This is why a0.makeB().add(a1.makeB()) type checks. This means that writing a nested class is equivalent to lifting that class definition out to the top-level and selectively hiding the name of the nested class.
Between different languages, there is a design chasm. In C++, there is only the unitary nested class and its associated semantics. Java distinguishes between static nested classes (similar to the C++ nested class) and inner classes. Java actually has a number of variants of nested classes (https://blogs.oracle.com/darcy/entry/nested_inner_member_and_top). The above C++ example translated into Java fails type checking because of A.B is private.

class A {
      private class B {

        public B add(B rhs) { val += rhs.val; return this; }
        private int val;

      }

      public B makeB() { return new B(); };
}

public class Nested0 {

   public static void main() {
     A a0 = new A();
     A a1 = new A();
     a0.makeB().add(a1.makeB());
   }
}

The call to add is flagged as a problem because a0.makeB()'s type (i.e., A.B) is inaccessible. If A.B were public or protected, however, the type checker is satisfied despite a0.B and a1.B supposedly denoting two distinct inner classes. Thus, at least at this point, inner classes do not provide abstract types in the sense of generative types.

On the other hand, as this discussion on Java decompilation (javap) shows, the semantics of inner classes are such that have a kind of C++

friend

relationship with their outer enclosing class. The discussion on TheServerSide shows how this is implemented: the compiler generates a static method that "breaks the encapsulation wall" to permit accessing private members of the outer class.

References

Herb Sutter wrote an article on nested classes in C++.