Tuesday, November 29, 2005
C++ annotations

download PDF from

Monday, November 21, 2005
Virtual Construtor in C++
Problem: In message passing environment, Getting the right class instantiated on the receiving end.

1. Tag each message class with a unique ID.
2. a global object pool consists of instance of each message class, i.e., each message class will rigister itself to this global object pool with an instance.
3. When getting a message, the tag is looked up and the new object will be created by CLONE (ing)

class Message {
static Message* newMessage( const Message& );
virtual Message* clone() const {
return new Message; // or return new Message( *this );

Message* Message::newMessage( const Message &prototype ) {
return prototype.clone();

class myMessage {
virtual Message* clone() const {
return new myMessage; // or return new myMessage( *this );

All you need to do is create an object of each class in the Message hierarchy and put them in a container class which can be searched. When
you receive a message, get the type ID and iterate on the container of Message objects until you find a match. Use that object as the argument to

void messageHandler( const messageStream &msg )
msg >> messageType;
Message* prototype = objectContainer.find( messageType );
Message* currentMsg = Message::newMessage( prototype );
msg >> ¤tMsg;

Sunday, November 20, 2005
Reading List

Lectures 1 and 2 - Should tables be sorted?
Should tables be sorted

Table Should be sorted (on random access machines)

Lectures 3 and 4 - Hashing: Universal and Perfect
Denial of Service via Algorithm Complexity Attack

Store a Sparse Table with O(1) Worst Case Access Time

Lecture 5 - Amortization and List Update Problem
Amortized Efficiency of List Update and Paging Rules

Lecture 6 - Disjoint Sets and Union-Find
Lectures 7 and 8 - Competitive Analysis and Paging
Amortized Efficiency of List Update and Paging Rules

Lectures 9 and 10 - Randomized Online Algorithms
Lecture 11 - Self-Adjusting Search Trees
Lecture 12 - Treaps: Randomized Search Trees
Lecture 13 - Skip Lists
Lecture 14 (part 1) - Caching Queues
Lecture 14 (part 2) - Self-Adjusting and Fibonacci Heaps
Lecture 15 -- Hashing for Massive/Streaming Data
Distinct Sampling for Highly-Accurate Answers to Distinct Value Queries and Event Reports. P. Gibbons. VLDB 2001.

Friday, November 18, 2005
Memory Model in multithreaded environment: broken double check locking
1. "The double-checked locking is broken" declaration


Double-Checked Locking:
1. an efficient method for implementing lazy initialization in a multithreaded environment. (Mostly used in Singleton pattern)

1. In Java, not work reliably in a platform independent way
2. In C++, depends on the memory model of the processor, the reorderings performed by the compiler and the interaction between the compiler and the synchronization library. Explicit memory barriers can be used to make it work in C++, but these barriers are not available in Java.

2. Discussing in memory model in multithreaded C++

1. C++ standard doesn't mention threads.
2. Threads added via libraries (e.g. pthreads).
3. Compiler mostly unaware of threads.
4. Synchronization calls treated as opaque.

Proposed Solution:
1. Atomic operations library
- load Atomically read the value of the integer.
- store Atomically replace the value of the integer.
- fetch and add Atomically add a value to the integer.
- store with release ordering semantics Atomically replace the value of the integer, and ensure that all prior memory operations executed by this thread become visible to other threads before the update.
- load with acquire ordering semantics Atomically load the value of the integer, and ensure that all later memory operations performed by this thread become visible after the load.

2. Memory model based on sequential consistency to avoid data race
- requires sequential consistency for ordinary variable accesses, but efectively allows reordering of atomic variable accesses when determining the existence of a data race, i.e. it tries to adapt the original solution.

3. Java approach
- sandbox execution of untrusted code
- ensure that no load of a shared pointer can ever result in a pointer to an object that was constructed with a different type. (This requirement will avoid the concurrent read-write confliction to a shared object)

3. Impact
an unavoidable impact on compiler optimization.7 Some currently common compiler optimizations need to be adapted to ensure thread safety. But this also reinforces
the urgency for thread support in C++

Thursday, November 17, 2005
csh script examples

#! /bin/sh
if [ x$URL = x ]; then

if [ x$I = x ]; then
while [ $I != 0 ]; do
I=$(( I-1 ))
linux2.4-glibc2.3-x86/dynamic_debug/test -u $URL -a 200K -t sync -f dummy -d get -i 1;

linux2.4-glibc2.3-x86/dynamic_debug/test -u $URL -a 2M -t sync -f dummy -d get -i 1;

Thursday, November 10, 2005
XPath pattern

section 5

Here are some examples of patterns:

Tuesday, November 08, 2005
XML schema validation in Java and schema design

1. RPC vs. Document

Quoted from

(1) Completeness

In RPC, the XML schema exists for each and every parameter with a definition to the parameter type but not to the message itself.

In Document, the XML schema available is applied for the whole message itself rather than the parameters alone. This is the functionality that lacks in RPC / Literal.

In RPC, apart from the schema that is available for the parameters there are other RPC rules required to send the data and receive the data across the wire and also to validate the message.

In Document, Each message contains no or one part. Each part points to a schema element definition that describes the whole content of the message in the SOAP body.

(2) Flexibility

In RPC, as the request message contains the element that contains the method name and its parameters there is a tight coupling between the consumer and the provider. So they don’t form a loosely coupled architecture when compared to Document / Literal style.

In Documents, as there are no mapping of method names and the parameters in both the request and response messages the coupling between the consumer and provider is very loosely coupled. The changes in the provider won’t affect the consumer to change.

2. Use XML validation in Java

Quoted from

Monday, November 07, 2005
XML Schema Design [ Best Practice ]

Quoted from


  1. Composition Vs. SubClassing


Conclusion: Like OO design, composition is to be favored over subclass. Composition approach leads to loosely coupled design. In subclassing approach, all subclasses are tightly bound together by a common root. In composition approach, we can put an empty element with an REF attribute to the placeholder where the actual element will go.


  1. Implementing Substitution Group element hierarchies

Conclusion: Substitution Group provides the capability of composition.

Let' recap what we've discussed: First declare the abstract element and its substitution group elements:

<xsd:element name="Publication" abstract="true" 
<xsd:element name="Book" substitutionGroup="Publication" 
<xsd:element name="Magazine" substitutionGroup="Publication" 

Next, declare a container type for each element, and have the container type holding the head element be the root of the type hierarchy:

<xsd:complexType name="PublicationContainer">
        <xsd:element ref="Publication" maxOccurs="unbounded"/>
<xsd:complexType name="BookContainer">
        <xsd:restriction base="PublicationContainer">
                <xsd:element ref="Book" maxOccurs="unbounded"/>
<xsd:complexType name="MagazineContainer">
        <xsd:restriction base="PublicationContainer">
                <xsd:element ref="Magazine" maxOccurs="unbounded"/>

Lastly, declare <Catalogue> to be of type PublicationContainer:

<xsd:element name="Catalogue" type="PublicationContainer"/>

Here's a sample instance document:


PublicationContainer contains an abstract element (Publication), so <Catalogue> must only contain elements that are in the substitution group with Publication, as we have shown here.

Because of the principle of type substitutability we can alternatively substititute the PublicationContainer type with a derived type. For example:

<Catalogue xsi:type="BookContainer">




Thursday, November 03, 2005
Stay Hungry, Stay Foolish
This is the text of the Commencement address by Steve Jobs, CEO of Apple Computer and of Pixar Animation Studios, delivered on June 12, 2005.

Powered by Blogger