Sponsorised links
February 2006
Chess Software Basics ( Flash )
Some fundas abt minimax principle, alpha-beta pruning
Symbol Tables and Search Tries : comp.compilers
Search Tries (?) are best for prefix searches. while hash tables, inspite of their resizes and collisions , can have an amortized cost of O(c) considering a random and uniform distribution hash function
Symbol Tables & Scope : Comp.compilers
How do you handle symbol tables for nested scopes ,ie, how to locate the symbol that is located deep in nested scope ( that may be declared multiple times ) ? Using a stack of symbol tables , having an invalid flag , having a tree ?
Sponsorised links
January 2006
Lisp is Sin
by 2 othersWhat are S-expressions ? What is that thing about "code is data and data is code"?
December 2005
Managed Code : Microsoft's Common Language Runtime (CLR)
Just got a glimpse of it..did not really sink in yet
October 2005
With a little help from your compiler - RLove blog
Just some GCC specific tricks
Functional Programming in Java
currying + function objects ( functors? )
Java performance related myths
by 1 otherHas a note on escape analysis and how crucial it is for Mustang :-)
LL(k) parsing
Nice refresher :). Left to right parsing with every step giving a leftmost derivation. k: Number of lookahead tokens
The ProtoThreads library
Stackless lightweight threads - blocking is explicit - local variables are not saved on context switch !!
Duff's Device
A mechanism for loop unrolling in C by using switch statement ( and the fact that case labels without break falls through )
C++ Exception Handling :Effect on Performance
Came here from comp.compilers. Reasons for perf hit :
(1) Have to call destructors of automatic objects when the stack is being unwound
Some methods of implementation :
1. Using setjmp ( for every try block to save the reg.state ) and using longjmp at the place of throw.
2.. Using tables for restoring context beforing entering catch block, to call dtors of automatic objects
many compiler optimizations can't be performed in presence of exceptions
[[[ did not read from landing pad onwards ]]]]
GCJ - The GNU Compiler for Java
by 2 othersFirst Ahead-of-time compiler that I am encountering. The thing is the Java runtime is linked into the executable ( libgcj is the GCJ runtime - hence a mixed interpreted/compiled binary is what u get )
PLDI2000: Field Analysis: Getting Useful and Low-cost Interprocedural Information
Makes use of the SSA Graph(?) - A number of inferences from field analysis like : Will a field refer to an object of an exact type and not any of its subclasses , will a field be initialized only once in a constructor, will a field be never used outside a constructor etc
Limitations : Native Methods, Reflection - can override access specifiers of classes (?), Java Memory Model - with weak consistency
Object Inlining - (1) Saves one pointer dereference (2) One less object for garbage collection . Only feasible when the objects share their lifetime ( get allocated and become dead at the same time )
Object Header - usually used for virtual method invocation [ by having a method table ], finding the type of the object , for synchronization operations
One other issue with object inlining is that if there is a reference to a an class which has number of subclasses then at runtime , the actual object's size might keep changing whenever the field reference is changed. This is not conducive to inlining. So we require that the reference is not changed once assigned
C++ : About Constructors and Static member declaration
Just came across this...to indicate that static members of a class have to have a SINGLE place of definition to prevent a linker error. Also refer the gcc-help mailing list
September 2005
Continuations in Java ( RIFE library )
Basically for interrupting your application using pause() and then continuing from where you left . Purported Use : In web applications instead of splitting form filling across multiple pages, could do in a single page while waiting for user interactions . ??
Java Alternatives : ( Mainly Ruby )
Could not understand most of it since no knowledge of Ruby - probably requires a second look once enuff is known about Ruby
RPC under attack
Dont confuse RPC with synchronous messaging- The Object-XML mapping problem ( mapping of XML data to native language objects is never complete ). Bulky data - too much blocking - JAX-RPC : Java API for XML based RPC ; Contract-First & Contract-Last interfaces ? ;
First time encountering C-omega !! ( C#'s externsion ) - it has anonymous structs with multiple fields having the same name - Has support for Query operators ( join, projection etc )
Six Different Types of Classes in Java
I was thinking of creating a static top level class for holding some Enum defintions but it turns out that there is no such thing as static top level class. Also, one interesting piece of code i had seen earlier was explained here : Anonymous classes !! [ Basically create an anoymous object implementing a known interface ]
Threads cannot be Implemented as Library
Importance of Threads - Servers + MultiProcessor onslaught ; Threads : need support from compiler + language.
register promotion ?
Using libraries for threads prevents usage of low-level features ( hidden by the library ) which affects performance. Sequential Consistency - difficult to implement , is strict. Moreover, compilers may reorder instructions to exploit parallelism b/n threads, h/w may reorder stores & loads.
Java + Pthreads : weak memory model. Pblms with pthreads : formal defintion of memory model not given, unlike java races can take place,
pthread_mutex_lock() for sync'ing memory rely on hardware insts to insert barriers to prevent compilers from moving
loads & stores across => not the best algorithmic solution + determining correctness depends on the behaviour of the
compiler ( in the absence of constraints imposed by the prog. language ).
Circular definition of concurrent modification : T1: if ( x == 1 ) y++; T2 : if ( y == 1 ) x++; //seq.model x=1 & y=1 not possible
if compiler transforms it to : ++y; if (x != 1) --y; ++x; if (y != 1) --x; // possible that x & y are both 1
Rewriting of adjacent data : especially in case of bitfields within structures.
Register Promotion : In the presence of speculative promotion of memory variables which are frequently accessed into registers moving across pthread_mutex_lock() calls
August 2005
comp.compilers : Information about profiling of OO Languages
Might be useful for TICD project
CC2003: Scaling Java Points-To Analysis using Spark
Subset Points-to Analysis (?) -
Escape analysis for object-oriented languages: application to Java OOPSLA'99
Idea of Escape Analysis - from Functional Languages - but imprecise results. Main Adv of this implementation : Less work for Garbage Collector, Saving Allocation Time
Fast Escape Analysis and stack allocation for object based systems (CC' 2000)
Use of SSA - direct control flow, Applications : Dead Store Removal, Iterator Reduction, Solution based on System of Constraints, Stack Allocation - replacement of new operator with newStack , Stack Allocation for objects within loops only if they have 'non-overlapping' lifetimes, Zeroing newly allocated objects - JVM spec, Object Reduction - local variables instead of fields, Object Inlining(?),
Advs : Less work for the memory allocator & garbage collector, increased data locality, optimizations enabled by doing object elimination (?)
Related Work : Escape Analysis for Functional Languages (!?)
