2008 Jul 03 - Thu
Upgrade from Eclipse Europa to Ganymede (with painful Subversion)
Today, I upgraded from Eclipse/CDT Europa to Eclipse/CDT Ganymede.
(CDT meaning C++ Developer Tools). The Eclipse upgrade was painless:
download the Eclipse/CDT package, expand it, and start eclipse from
within the directory. After pointing it to my workspace, everything
was there. Nicely simple.
My subversion client was an entirely different story. For the Europa installation,
everything came from the tigris site and worked well. For the Ganymede installation,
there are now two sites involved, and I'm not sure which is what. I think
the tigris site can now be ignored (for the time being). In the
installation instructions somewhere, one needs to go to the
Polarion site for their client. There
are Eclipse update links there.
However, what I assumed to be workable defaults of using the JavaHL library on
Debian turned out to be non-workable. The solution was not to use the JavaHL
client but use the SVNKit client.
My key problem is that my SVN repository requries an ssh public/private key.
The JavaHL library, if or when it would or wouldn't load, I'm not sure what I was
seeing, but I could only see the option for user name and password authentication.
It would have been nice if the Subversion/Polarion/Eclipse guys would all get
together and make it straight-forward in terms of which libraries from
which sites need to be download. If they imply that the JavaHL libraries should
be downloaded, please make it painless to get the paths set and ensure the binaries
are present. After 15 million lines of code, you'd think that would be a
small task to accomplish.
2008 Jun 17 - Tue
Concurrency aka MultiThreading
A number of my projects are approaching the phase where some of their feature sets
will work better with some form of background processing. In a trading application,
plowing through historical data on thousands of symbols looking for patterns would be
best left to a background task, rather than rendering the user-interface frozen during
the, well, duration. For Radius, with a listener on an accounting port, and one on an
authorization port, the two threads need to coordinate access to resources.
Windows has a native threads API, but that isn't necessarily portable between operating systems.
My trading application is in Windows, and the Radius application in on Linux. Using the same API on both
platforms wuold be cool.
As I already use the Boost tools in their various forms, Boost::Thread would be a good candidate.
The Boost documentation isn't exactly overflowing with examples. Dr. Dobb's Portal
saves the day with an article dating from May 2002 entitled
The Boost.Threads Library.
It has good examples covering the basics:
- Thread Creation (boost::thread)
- Mutexes (boost::mutex), which protects one thread from another
- Condition Variables (boost::condition), which are good for getting data into and out of a thread
- Thread Local Storage (boost::thread_specific_ptr), for keeping thread specific storage separate from other threads
- Once Routines (boost::call_once), for making sure statics are initialized once and only once
For mutexes, protecting code regions can be as easy as declaring a mutex:
boost::mutex CodeProtectionMutex;
And then putting a scoped lock in the code encountered by multiple threads:
{ // some scope some where
// ... some code
boost::mutex::scoped_lock lock(CodeProtectionMutex);
// .. some more code, which is protected by the lock
} // the scope exit, no unlock is required as the destructor does the work
After reviewing the examples, making use of the Boost documentation should be an easier
task. As such, boost::thread documentation should be reviewed anywa as boost::thread
has gone through some changes since that article.
Paul Bridger has also written a
tutorial on multithreading making use of the boost::thread
class. The navigation through the tutorial isn't the greatest, but the content is good.
Making use of boost::thread as a base, Philipp Henkel has written
threadpool. It has been
brought up to date for use with boost v1.35. It provides a dead easy solution to
making use of a limited number of worker threads to carry out tasks:
pool tp(2); //create a 2 thread pool
// Add some tasks to the pool.
tp.schedule(&first_task);
tp.schedule(&second_task);
tp.schedule(&third_task); // this task waits until of the other two completes
In the similar vein to Henkel, Ted Yuan has a boost::thread based
C++ Producer-Consumer Concurrency Template Library.
Zoltán Porkoláb has written an article on
Distributed Programming and Metaprogramming in C++. It has many
examples and goes into some additional examples for boost::thread. His article also
introduces bind and tuples, which are good backgrounds to boost::lambda.
Back to boost for a second. You can't find it from the boost home page, but here is a
good link to
Boost Libraries Listed Alphabetically.
boost::thread is a basic threading library. Going above and beyond multi-threading
grunt work, Intel's
Thread Building Blocks has higher level constructs for getting
multiple threads going. For example, it has a 'for' construct for simultaneously
executing multiple elements of the for statement. Good tutorials and background
information can be read through
Kevin Farnham's Blog.
Building further on the Threading Building Blocks is something of
simulating interest:
go parallel looks to be chock full of content related to multi-core and multi-threaded
programming.
From the theoretical perspective, I came across an HP paper called
Foundations of the C++ Concurrency Memory Model, and written by Hans-J. Boehm and Sarita V. Adve.
I havn't read it all the way through, but at some time, I think the bibiliography may be
a worthy read in itself.
2008 Jun 16 - Mon
Keyword Matching (non-text streams)
In a previous blog article, I presented the beginnings of a Keyword Lookup class. This
article takes that work, turns it into a template and makes it useful for longest match
lookups.
I'll have to compare this lookup library with what a C++ map or unordered_map does for
lookup speed. I'm hoping that when a comparison is made, that this routine is indeed
faster. I'm thinking it might be because, even though a map will do a binary search through
it's map, complete strings are compared at each step. With this library, keyward patterns
are added to a rooted tree of characters, possibly reducing the amount of time spent
mactching.
I must admit that at each match step, there is a linear search performed through a list
of likely character candidates. To imporve the search, I've been thinking that once the
pattern tree has been
created, it could be sorted so that each step search can be done with a binary search. This
will be something for next time.
In the meantime, this routine does work for finding maximum matches. For example when
performing a long distance rate lookup, this will find the most specific rate code from a
list of various length candidates, something which is difficult to do with a map.
This keyword match algorithm is template based. 'class T' is the type to be returned
upon a successful match. It can be an index, a pointer, a number, or anything else
suitable. The class constructor requires an initializer... basically a value to be given
the equivalent meaning of NULL. On no match, this value is returned. Use 'AddPattern' to
add patterns and their associated 'meanings'. Use FindMatch to perform the lookup.
// this is kind of a subset of Aho Corasick algorithm
// only full keyword matching, no text searches
// no on failure coding
#ifndef CKEYWORDMATCH_H_
#define CKEYWORDMATCH_H_
#include <string>
#include <vector>
#include <stdexcept>
#include <iostream>
template<class T> class CKeyWordMatch {
public:
explicit CKeyWordMatch<T>( T initializer, size_t size );
virtual ~CKeyWordMatch(void);
void ClearPatterns( void );
void AddPattern( const std::string &sPattern, T object );
T FindMatch( const std::string &sMatch );
size_t size( void ) { return m_vNodes.size(); };
protected:
T m_Initializer;
struct structNode {
size_t ixLinkToNextLevel; // next letter of same word
size_t ixLinkAtSameLevel; // look for other letters at same location
T object; // upon match, (returned when keyword found)
char chLetter; // the letter at this node
explicit structNode( T initializer ) : ixLinkToNextLevel( 0 ), ixLinkAtSameLevel( 0 ),
object( initializer ), chLetter( 0 ) {};
};
std::vector<structNode> m_vNodes;
private:
};
template<class T> CKeyWordMatch<T>::CKeyWordMatch( T initializer, size_t size )
: m_Initializer( initializer )
{
m_vNodes.reserve( size );
ClearPatterns();
}
template<class T> CKeyWordMatch<T>::~CKeyWordMatch(void) {
m_vNodes.clear();
}
template<class T> void CKeyWordMatch<T>::ClearPatterns() {
m_vNodes.clear();
structNode node( m_Initializer );
m_vNodes.push_back( node ); // root node with nothing
}
template<class T> void CKeyWordMatch<T>::AddPattern(
const std::string &sPattern, T object ) {
std::string::const_iterator iter = sPattern.begin();
if ( sPattern.end() == iter ) {
throw std::invalid_argument( "zero length pattern" );
}
size_t ixNode = 0;
size_t ix;
bool bDone = false;
while ( !bDone ) {
char ch = *iter;
ix = m_vNodes[ ixNode ].ixLinkToNextLevel;
if ( 0 == ix ) { // end of chain, so add letter
structNode node( m_Initializer );
node.chLetter = ch;
m_vNodes.push_back( node );
ix = m_vNodes.size() - 1;
m_vNodes[ ixNode ].ixLinkToNextLevel = ix;
ixNode = ix;
}
else { // find letter at this level
bool bLevelDone = false;
size_t ixLevel = ix; // set from above
while ( !bLevelDone ) {
if ( ch == m_vNodes[ ixLevel ].chLetter ) {
// found matching character
ixNode = ixLevel;
bLevelDone = true;
}
else {
// move onto next node at this level to find character
size_t ixLinkAtNextSameLevel
= m_vNodes[ ixLevel ].ixLinkAtSameLevel;
if ( 0 == ixLinkAtNextSameLevel ) {
// add a new node at this level
structNode node( m_Initializer );
node.chLetter = ch;
m_vNodes.push_back( node );
ix = m_vNodes.size() - 1;
m_vNodes[ ixLevel ].ixLinkAtSameLevel = ix;
ixNode = ix;
bLevelDone = true;
}
else {
// check the new node, nothing to do here
// check next in sequence
ixLevel = ixLinkAtNextSameLevel;
}
}
}
}
++iter;
if ( sPattern.end() == iter ) {
if ( m_Initializer != m_vNodes[ ixNode ].object ) {
throw std::domain_error( "Pattern already present" );
}
m_vNodes[ ixNode ].object = object; // assign and finish
bDone = true;
}
}
}
template<class T> T CKeyWordMatch<T>::FindMatch( const std::string &sPattern ) {
// traverse structure looking for matches, object at longest match is returned
std::string::const_iterator iter = sPattern.begin();
if ( sPattern.end() == iter ) {
throw std::runtime_error( "zero length pattern" );
}
T object = m_Initializer;
size_t ixNode = 0;
size_t ix;
bool bDone = false;
while ( !bDone ) {
char ch = *iter;
ix = m_vNodes[ ixNode ].ixLinkToNextLevel;
if ( 0 == ix ) {
bDone = true; // no more matches to be found so exit
}
else {
// compare characters at this level
bool bLevelDone = false;
size_t ixLevel = ix; // set from above
while ( !bLevelDone ) {
if ( ch == m_vNodes[ ixLevel ].chLetter ) {
if ( m_Initializer != m_vNodes[ ixLevel ].object )
object = m_vNodes[ ixLevel ].object;
ixNode = ixLevel;
bLevelDone = true;
}
else {
ixLevel = m_vNodes[ ixLevel ].ixLinkAtSameLevel;
if ( 0 == ixLevel ) { // no match so end
bLevelDone = true;
bDone = true;
}
}
}
}
++iter;
if ( sPattern.end() == iter ) {
bDone = true;
}
}
return object;
}
#endif /*CKEYWORDMATCH_H_*/
2008 Jun 15 - Sun
Mean Reversion Thoughts
While still putting together the code for a trading solution, I've been thinking about
what algorithms to implement for a trading strategy. I have access to live intra-day tick
and quote data, so mean-reversion aka contrarian strategies seem like interesting
candidates.
In the course of manual trading, I've learned that one needs to keep track of a number of
items: current portfolio costs, current holding costs, existing profit/losses, expected
market direction, current market location, external influences. This is a lot to do
manually. Hence the desire to implment tools to automate, or even semi-automate the
process.
A paper by Subramanian Ramamoorthy called
A strategy for stock trading based on multiple models and trading rules
discusses a state space mechanism for determining how to manage the portfolio composition.
Another item he brings to the foreground is a description of the Sharpe Ratio, a ratio which
helps one to keep profit consistent rather than widely dynamic.
Using different terminology, the makers of NeoTicker have a blog with an article called
Counter-Trend Trading with Simple Range Exhaustion System. The key point, which could
be hard to do, is "most counter-trend traders will try to time their entries as close to the
extreme reversal points as possible to maximize the profits and minimize the risk
exposures". Using multiple time frame charts, and
reading the tape, along with some possibly helpful technical analysis tools, it might be
possible to home in on the zones of reversal.
Working my way into a little scalping in the futures, an older article at Interactive
Brokers explains the birth of the
Dow Mini Futures. Some interesting points:
- "try to identify the leader in a group and how its price movement can help us predict
movement in others in the group"
- "we start to trade it by hand so we can get a better understanding of the nuances in
that particular trade"
- "We have a trader and a programmer trade together for a while and then we start the
process of automation. We define our risk parameters and write the rules that we feel give
us an opportunity to be profitable."
- "In our back testing we saw that if we were patient it would be profitable for us. The
hard part was learning to be patient because our other successful trades were very high
frequency. In the mini-sized Dow we may be in and out of 5 to 10 trades in a less than
minute."
- hedge the mini dow with the underlying basket of stocks
- "We don't have scalping targets. We generate a theoretical value and make markets
based purely on that value If we our pricing is accurate and we should naturally be able to
scalp."
- "In the Dow because the bid-ask spread is so tight most of our profits are generated
from trading."
- "he dow has a much tighter spread compared to the mini-spu. Also it is much easier to
watch the stocks in the underlying basket to ascertain their effect on the future."
- "The Russell tends to be trendier than other indices."
Adaptive Arrival Price
A keynote lecture at the April 7th Algorithmic Trading Conference in London was by Mr.
Julian Lorenz of ETH Zurich. The abstract for his lecture reads as follows:
Electronic trading of equities and other securities makes heavy use of "arrival price"
algorithms, that balance the market impact cost of rapid execution against the volatility
risk of slow execution. In the standard formulation, mean-variance optimal trading
strategies are static: they donot modify the execution speed in response to price motions
observed during trading. We show that with a more realistic formulation of the mean-variance
tradeoff, with no momentum or mean reversion in the price process, substantial improvements
are possible by using dynamic trading strategies. We develop a technique for computing
optimal dynamic strategies to any desired degree of precision. The asset price process is
observed on a discrete tree with a arbitrary number of levels. We introduce a novel dynamic
programming technique in which the control variables are not only the shares traded at each
time step, but also the maximum expected cost for the remainder of the program; the value
function is the variance ofthe remaining program. The resulting adaptive strategies
are"aggressive-in-the-money": they accelerate the execution when the price moves in the
trader's favor, spending parts of the trading gains to reduce risk. The improvement is
larger for large initial positions.
I think I'll add 'arrival price algorithms' to my key word searches. The above extract
was from a search on 'mean reversion trading system algorithms'.
2008 Jun 08 - Sun
Stocks & Commodities, 2008/06
In a recent issue of Technical Analysis of Stocks and Commodities, there was an interview
with Tom Busby. A number of his comments struck home with some things I've learned. He
also introduced a few more things about which I should think.
He noted that trading can be a twenty four hour operation. There is always some market
open to trade. The world starts off with the Nikkei and the Hang Seng in the far east. In
Europe, primary markets are CAS, FTSE, DAX and the Swiss. I'd say in today's market the
IPE, with the Brent Crude Futures, is also important. Here in the west, we have the morning
New York market and the afternoon California market.
Busby made mention that 'market open' is an important event. As such, it is important to
know the time each of the markets open. I've been working on an algorithm that selects a
series of instruments, selects a direction and lets the instruments run. I've been
wondering what to set for an exit though. Busby, in the interview,
suggests exiting once a third of ATR
(Average True Range) has been reached. I'm not sure why he would use ATR (which accounts
for any opening gap) rather than just the daily average range. Assuming one gets in
sometime in the open, and exits by the end of the day (in order to eliminate what gaps in
the wrong direction can do to one's portfolio), then using ATR doesn't seem quite right.
Anyway, To set the tone for a trading day, he suggests some benchmark indexes to be
watched. Seven, which he calls the Seven Sisters are:
- S&P
- NASDAQ
- Dow Jones Indexes
- DAX
- Crude Oil
- Long Bonds
- Gold
As for micro-signals, he uses three kinds, with each needing to be in the same direction:
- Volume
- Tick (gainers vs loser)
- Trend
To finish things off, he suggests splitting an entry into three parts:
- Tick Part: the trickiest part of the entry based upon the three variables above
- Trade Part: with confidence building, try to make twice the reward vs risk
- Trend Part: capture the full movement of the day
2008 Jun 06 - Fri
SmartQuant QuantDeveloper & DataCenter Release
SmartQuant has released a revision
to DataCenter and
QuantDeveloper. DataCenter and QuantDeveloper are at the following revision levels:
DataCenter
Version 3.0.2 (06-Jun-2008)
QuantDeveloper Enterprise Edition
Version 3.0.2 (06-Jun-2008)
QuantDeveloper Source Code
Version 3.0.1 (21-Apr-2008)
* Recent Versions available through
version control
Wt, Some Build Modifications
Back on
2007/10/03, I wrote about installing Wt (a C++ library and application server for
developing and deploying web applications) on a Debian server. I've revised things a little
bit since thing while building Wt v2.1.3.
In this case, I build with the newly released version of the Boost libraries: 1.35.
ASIO is now included in Boost, so some build steps can be removed.
Prerequisites are little changed but for a different library for gd:
apt-get install gcc
apt-get install zlib1g
apt-get install zlib1g-dev
apt-get install libbz2-dev
apt-get install libgd2-noxpm-dev
apt-get install cmake
apt-get install libfcgi-dev
apt-get install libapache2-mod-fastcgi
apt-get install libssl-dev
The web site and repository for Wt have changed, so CVS commands will be a bit different:
cvs -d :pserver:anonymous@cvs.webtoolkit.eu/opt/cvs login
cvs -z3 -d :pserver:anonymous@cvs.webtoolkit.eu/opt/cvs co wt
I've changed the cmake/build a little bit so the results go into /usr/local/wt/include
and /usr/local/wt/lib:
cmake -D DEPLOYROOT=/var/www/wt -D WEBUSER=www-data -D WEBGROUP=www-data \
-D BOOST_DIR=/usr/local \
-D BOOST_COMPILER=gcc42 \
-D BOOST_VERSION=1_35 \
-D BOOST_INCLUDE_DIR=/usr/local/include/boost \
-D BOOST_LIB_DIR=/usr/local \
-D BOOST_DT_LIB_MT=/usr/local/lib \
-D BOOST_DT_LIB=/usr/local/lib \
-D BOOST_FS_LIB=/usr/local/lib \
-D BOOST_FS_LIB_MT=/usr/local/lib \
-D BOOST_PO_LIB_MT=/usr/local/lib \
-D BOOST_REGEX_LIB_MT=/usr/local/lib \
-D BOOST_SIGNALS_LIB_MT=/usr/local/lib \
-D BOOST_THREAD_LIB=/usr/local/lib \
-D BOOST_ASIO_INCLUDE_DIR=/usr/local/include/boost \
-D SHARED_LIBS=ON \
-D CONNECTOR_FCGI=OFF \
-D CONNECTOR_HTTP=ON \
-D EXAMPLES_CONNECTOR=wthttp \
-D WTHTTP_CONFIGURATION=/etc/wt/wthttpd \
-D CONFIGURATION=/etc/wt/wt_config.xml \
-D CMAKE_INSTALL_PREFIX=/usr/local/wt \
.
During make install, an error regarding CMakeFiles arises. The secret, that I know, is
to remove the line which includes CmakeFiles in src/Ext/cmake_install.cmake, and restart
'make install'. The install should complete normally.
The library directory /usr/local/wt/lib will need to be added to /etc/ld.so.conf, and
then run ldconfig to update things.
Remember to review the
Ext widgets deployment page as there are some additional files to be downloaded and
installed from Ext JS.
2008 Jun 04 - Wed
PostgreSQL Upgrade 8.2 to 8.3
Back in Febrary, I wrote a longish article on how to upgrade PostgreSQL. That article is
outdated. An upgrade can now take place with two lines:
pg_upgradecluster -v 8.3 8.2 main
pg_dropcluster 8.2 main
The first copies the older version 8.2 files to the new 8.3 files directory. It does any
modifications necessary. The second line then removes the old stuff.
2008 Jun 03 - Tue
OpenSSH Issues
In light of the not so recent news regarding the vulnerability of openSSH in Debian, many
systems have had to be patched and inter-machine keys changed.
Via
Steven Rosenberg's Site I learn that a simple 'apt-get update && apt-get dist-upgrade'
will update the necessary files on my system. Also in the blog entry is a reference to
DRONEBL which is another black list site
dealing with root compromised sites. A commenter posts the following interesting remarks
about further protecting a server:
If you aren't running fail2ban or denyhosts, you should. Both will detect brute force
attempts and deny connections from the attacker for a time. If you feel uncomfortable
automatically banning hosts for failed logins, you can weakly configure whichever you choose
to allow 20 or more failed attempts before banning. There's no reason any authenticated
service should tolerate brute force attempts, in my humble opinion.
Finally, there are services, such as the DroneBL dnsbl, which have honeypot servers set
up to detect brute force attempts and add them to a blacklist. You can use the "aclexec"
directive in hosts.deny to query this blacklists before allowing clients to connect, to
prevent connections from known brute force attackers. See http://headcandy.org/rojo/ for a
suitable script to call via aclexec (view the source for the checkdnsbl script for usage
instructions), and see the man page for hosts_options for more info.
Running 'ssh-vulnkey -a' showed that there were a couple keys that needed to be
deleted and/or redone.
Debian has a
WIKI with good information
regarding the problem, affected programs, and utilities to help determine where the problems
are.
If weak keys have been copied to other non-Debian hosts, the keys need to be removed
from those hosts as well.
|