Project Ideas

1. CL implementations of algorithms specified in the Unicode standards;
2. Integration of these algorithms into the the SBCL language runtime;
3. Integration of test cases into the SBCL build sequence;
4. Exploratory work in using these algorithms in suitable places in the Lisp language runtime.

There are no hard prerequisites for this project; an interest in internationalization issues would be helpful, as would prior experience with working with Unicode.

A student successfully executing this project would learn about: data structures for efficient information storage; test methodologies; and working within the strictures of standardized algorithms and languages.

1. (partial) Foreign function interface definitions for GMP;
2. Development of routines to convert between two's complement and sign-magnitude representation;
3. Integration in SBCL's existing bignum and rational arithmetic code;
4. Determination of criteria for the use of GMP's routines to improve performance on large integer or rationals, as used in applications, without overly penalising the common case of tiny values;
5. Development of unit tests for the new routines;
6. Improvement of SBCL's algorithms for small or medium bignums and rationals (optional).

Familiarity with Common Lisp or C. An interest in number theory would be useful, and may provide additional motivation.

The student would learn to characterise the use of a small part of a system (bignum and rational arithmetic) by various applications, and develop microbenchmarks accordingly, in order to make non-obvious technical decisions. They would also exercise test methodologies, and potentially implement algorithms described by specialised scientific literature.

Code by Waldek Hebisch http://comments.gmane.org/gmane.lisp.steel-bank.general/3273 http://www.math.uni.wroc.pl/~hebisch/prog/

It seems like using GMP can help FriCAS a lot https://groups.google.com/forum/#!msg/fricas-devel/yby-B4QS4b4/3VFvYRomWQAJ

Pi digits on the benchmarks game is currently a bunch of calls to GMP. It would be nice to have comparable performance with portable CL. http://benchmarksgame.alioth.debian.org/u64q/program.php?test=pidigits&lang=sbcl&id=1

1. Implementations of several classes of random number generators, including one statistically-robust PRNG, geared toward demanding mathematical applications, and one believed suitable for cryptographic applications;
2. Use of statistical tests to examine the properties of the implemented PRNGs;
3. Pluggable integration into SBCL's existing random number generation code (using random-state objects);
4. (optional) support for hardware random number generators;
5. (optional) development of a protocol to allow random number generators to be selected dynamically given algorithmic requirements.

No strict prerequisites, although some understanding of the possible space of pseudorandom number generation, including tradeoffs regarding speed, predictability (forwards and backwards) and dimensional distribution. Familiarity with CL and its approach to random number generation can be acquired while doing the project.

The student will learn the breadth of possible implementations of random number generators, and their limitations, all while working in the context of an established language runtime. A successful project is also likely to cover statistical tests of randomness and efficient object-oriented design.

1. A list of promising vectorisable operations;
2. The implementation of a few special cases for such vectorisable operations;
3. A generic method to dispatch to vectorised routines depending on the CPU's capabilities;
4. (optional) Convenience macros and functions to implement complete vectorised operations, including misaligned data;
5. (optional) SIMD-within-a-register (SWAR) implementations for some vectoriable routines.

Understanding of the bit-level representation of data in computers. Familiarity with SSE instructions is expected to improve with time.

The student will learn to detect opportunities for vectorisation in pre-existing code. They will also hone their ability to adapt algorithms to vector processing, and develop methods to determine when and how operations should be vectorised.

1. Adapt and implement known families of hash functions for integer and string data;
2. Improve the distribution of standard hash functions;
3. Implement routines to test the quality and correctness of hash functions;
4. (optional) Provide parameterised hash functions that are resistant to collision attacks, as extensions to the standard;
5. (optional) Implement specialised associative dictionaries.

Familiarity with probabilities and with basic data structures. An interest in computer microarchitecture will be useful.

The student would exploit or implement state of the art hash functions, compare their strengths and weaknesses, and integrate them in a complete system. They would also apply their understanding of the low-level representation of data to develop specialised data structures that remain compatible with a specification.

1. Disentangle or replicate the front-end to perform minimal compilation;
2. Define an intermediate representation appropriate for the efficient interpretation of Common Lisp code;
3. Develop a compiler from minimally-compiled source to the intermediate representation.

Familiarity with Lisp macros and with first-class functions.

The student would improve their ability to read, understand, and implement an ANSI standard. They would then explore the performance of a few standard or novel interpretation schemes on contemporary computers. Finally, they would develop a small compiler for a practical programming language.

"Using closures for code generation," Feeley M and Lapalme G (http://www.iro.umontreal.ca/~feeley/papers/FeeleyLapalmeCL87.pdf) nicely presents a technique that's very useful to compile languages without writing a full native code compiler. That's how CL-PPCRE compiles regular expressions.

1. Collect, organise, and diagnose concurrency bugs in PCL;
2. Fix some of these bugs;
3. Develop a methodology to trigger hard-to-detect concurrency bugs in PCL;
4. Suggest generally-applicable techniques to eliminate such bugs from PCL and the runtime system (optional).

Basic understanding of shared-memory concurrency. A conservative understanding of specific memory models will be developed in parallel with the work.

The student will encounter concurrency bugs in a complex stateful system that exploits both lock-based concurrency control and lock-free operations. They will develop an understanding for the issues encountered in such systems, and learn how to detect and then solve them.

1. Survey of proven threading/locking debugging tools;
2. Implementation and integration of at least one such tool in SBCL;
3. Documentation for these extensions;
4. (optional) Suggestion of alternative less error-prone constructs for sb-concurrency or sb-thread.

Familiarity with the POSIX threads programming model. An awareness of the execution process for multi-socket systems with multiple levels of cache would be useful, but not necessary.

The student would become intimately familiar with the sort of bugs commonly encountered in threaded system. They would also study state of the art tools to detect such bugs, and replicate some of them for integration in a pre-existing environment. They would also exercise their technical writing skills to document the tools and describe their correct use. Finally, they would demonstrate the ability to propose elegant architectural solutions to complex issues.

1. Implement strength reduction of signed truncated division;
2. Determine how to correctly simplify floor and ceiling division;
3. Implement strength reduction of floor and ceiling division;
4. Adapt the algorithms to take tagging into account;
5. Extend the test suite for integer division by constants;
6. (optional) Extend the work to constant division by rationals.

Basic number theory. Some work will likely be at the assembly level, but what little is necessary can be acquired on the fly.

The student would apply pure mathematics concepts from number theory to understand how to correctly simplify operations in computer programs. They would likely become acquainted with the performance characteristics of contemporary computers to decide how to let number theory guide the simplification of divisions by integers. They would also show the correctness of simple but novel variations, and exploit their understanding of the problem domain to develop tests that are likely to detect incorrect transformations.

"Integer division using reciprocals," R Alverson (http://www.acsel-lab.com/arithmetic/papers/ARITH10/ARITH10_Alverson.pdf)

"Division by invariant integers using multiplication," T Granlund and PL Montgomery (http://gmplib.org/~tege/divcnst-pldi94.pdf)

"N-Bit unsigned division via N-Bit multiply-add," AD Robison (http://www.computer.org/csdl/proceedings/arith/2005/2366/00/23660131-abs.html)

"Labor of Division (Episode III): Faster Unsigned Division by Constants," ridiculous_fish (http://www.ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html)

Specifically on extension to floor/ceiling http://discontinuity.info/~pkhuong/misc/div-by-mul.pdf

Some of the references above were first found via http://www.mail-archive.com/open64-devel@lists.sourceforge.net/msg01139.html. It seems like work in this area tends to be duplicated… A review might not hurt.

Hacker's Delight might be more confusing than anything else, YMMV (also, see http://www.hackersdelight.org/divcMore.pdf).

1. Forward-port the indirect-jump patch;
2. Expose the new operator in a standard-compliant manner;
3. Create benchmarks to understand how to best use this new operator;
4. Exploit the operator in the implementation of standard flow control macros;
5. (optional) For the patch to additional computer architectures.

Knowledge of x86[-64] assembly language. Familiarity with advanced compilation techniques is an advantage.

The student would gain an overview of the complete pipeline in a production compiler, from the front-end, to dataflow analyses, to the generation of machine code. They would also have to work within an ANSI standard to expose a new feature to users. Finally, they would improve their understanding of the low-level performance of modern architectures, particularly at the level of branch prediction, in order to transparently improve the runtime efficiency of flow control constructs.

This dates from 2008, but it gives a decent idea of how little code is needed to get started http://discontinuity.info/~pkhuong/sbcl-switch-case.lisp.

1. A naïve but clearly correct interval derivation module;
2. Development of test cases to trigger issues in numeric (floating-point) type derivation;
3. More sophisticated interval derivations;
4. (optional) Express the interval derivation logic in portable Common Lisp for the cross-compiler.

Some real analysis. Minimal familiarity with numerical analysis and with the implementation of floating-point arithmetic in computers.

The student will bridge between their understanding of mathematical operations with their concrete approximation in contemporary computers to safely characterise the behaviour of arbitrary Common Lisp expressions. They will thus acquire experience with simple numerical analysis, and become acquainted with the difference between theoretical mathematics and floating-point operations. They will also learn to exploit the concrete representation of floating-point values to implement simple and efficient, but correct numerical algorithms.

1. Detection and visualisation of expression trees in the first intermediate representation (IR1);
2. Insertion of a top-down rewriting pass in the IR1 optimisation loop;
3. Development of a pattern and transform definition language for expression trees;
4. Implementation of a few rewrites with this new infrastructure.

Basic discrete mathematics. Familiarity with formal grammars and automata theory is optional.

The student would improve their understanding of the compilation process for pure expressions, and review, then implement, classic techniques for their improvement. They would also develop a new internal library feature, and exploit it to show concrete improvements in the compiler's output.

1. Gather example code that exercises SBCL's type-based analyses;
2. Determine what operations exhibit complexity blowups in these examples;
3. Define a simple type widening operator, and insert it in key places;
4. Experiment with various widening strategies and alternative type lattices to improve compilation speed while preserving correctness and reasonable execution efficiency.

Proficiency in discrete mathematics, particularly set theory. The student is expected to become familiar with data flow analyses in the course of the project.

The student will acquire experience at profiling a complex symbolic manipulation system. They will then apply their results to improve the practical performance of the system, while preserving its mathematical correctness. They will also strengthen their mastery of the static (data flow) analysis of impure languages.

1. Identify the most time-consuming phases of the compiler;
2. Extend performance and correctness tests for the compiler;
3. Determine how to disable or simplify time-consuming phases, while preserving correctness;
4. (optional) Develop alternatives for a few recursive or super-linear computations in the compilation process.

No strict prerequisite. An interest in compilation would be helpful, as would familiarity with the analysis and design of algorithms and data structures. The student will become comfortable with set and lattice theory.

The student will gather representative code samples from actual users, and exploit them to build an understanding of the empiric performance of SBCL's compiler. They will also use this data to develop benchmarks that reflect real-world needs, and design tests to convince themselves and others that changes to a large system preserve its correctness. They will finally exploit these tools to determine which parts of the compiler should be disabled or simplified, and how to do so.

Short IRC transcript on the topic

06:53 < pkhuong> I believe you had some stuff on quicker compilation? Is there any preliminary branch, patch set or notes I should point people to?
07:01 <@nikodemus> pkhuong: not as such
07:02 <@nikodemus> i can write a quick braindump
07:02 <@nikodemus> IIRC. the biggest timesink is constraint propagation.
07:03 <@nikodemus> IIRC. the trickiest thing about eliminating it is that we have a bunch of places that assume that certain things are always optimized.
07:03 <@nikodemus> so if you eliminate it, you get "correct" code that the rest of the system cannot deal with
07:05 <@nikodemus> being a silly young thing, i was working on essentially adding IR0 which would have been a fast way to get those minimal things sorted out. I still think that's possible, 
                   but it probably isn't the best way to go about it...
07:07 <@nikodemus> i think it would be a reasonable approach to just diable it, and see where things break, and start fixing the places that make those assumptions
07:07 <@nikodemus> EOBD
07:07 <@nikodemus> s/diable/disable/
07:09 < pkhuong> sounds right to me as well.
07:12 < pkhuong> So, I see where constraint propagation can be simplified... we need quick but conservative type union/intersection... csubtypep as well, I guess.
07:13 < pkhuong> Then, see what happens to the transforms, and play whack-a-mole.
07:13 <@nikodemus> IIRC a typical breaked is from eg (coerce x 'list) => (the list (if (listp x) x (convert-to-list x))) sort of transforms
07:14 < pkhuong> how does that break?
07:15 <@nikodemus> don't remember the details. maybe when X is known not to be a list due to a declaration?
07:16 <@nikodemus> so you end up with something like (the list (the (not list) x))
07:16 <@nikodemus> which the compiler won't like
07:16 <@nikodemus> or maybe it was IR1-OPTIMIZE that was needed to kill the IF
07:17 < pkhuong> oh yeah.
07:17 < pkhuong> constraints need ir1 optimise to kill (if [x] [block] [same block]) into (progn [x] [block])
07:19 <@nikodemus> and (if [always false] [will cause a runtime error] [ok])?
07:19 <@nikodemus> because some of the breakaged were WARNINGs due to compiler thinking it sees something that will break at runtime for sure
07:19 <@nikodemus> breakages, even
07:19 < pkhuong> I think that's all right, wrt codegen. I changed that to style warnings because of ppcre
07:20 <@nikodemus> oh
07:20 < pkhuong> If there's a branch on the path (well, it's a hack, but catches most cases), the warning is downgraded to a style warning.
07:21 <@nikodemus> right
07:21 <@nikodemus> then there are our always-translatable things, i guess
07:22 < pkhuong> shouldn't we get nearly all of those right just with the defknowned types?
07:22 <@nikodemus> and many many transforms which should not be done unless we're actually going to compile things as well as we can
07:22 <@nikodemus> most, i think
07:22 < pkhuong> there's that. workingness would be a good first step though (:
07:23 <@nikodemus> and the rest should probably not be always-translatable, but something like mostly-translatable :)
07:23 < pkhuong> right.
07:24 <@nikodemus> yeah, and eliminating transforms is the completely wrong first step, because /almost/ any problematic code a transform can inject can also come from a user
07:25 <@nikodemus> though i'm willing to give a pass to eliminating transforms that produce (sb-foo:%something-magic ...) if they turn out to be a problem
07:25 < pkhuong> yes and no... We could only run CP once. User code would benefit from minimal constraints, but deftransformed code not.
07:26 <@nikodemus> sure, but in deep CMUCL time CP used to be completely optional
07:26 <@nikodemus> i'd sort of like to restore that
07:26 < pkhuong> right.
07:26 <@nikodemus> oops. make that "would like to see that restored" :)
07:27 < pkhuong> Also, our transforms go out of their way to depend on CP: expand into a lambda without type declaration on the arguments?
07:28 <@nikodemus> the deftransform could magically add most of the type information there, i think
07:28 <@nikodemus> (a case for truly-type declaration?)

1. Code samples exhibiting disastrously weak type derivation;
2. A correct and probably very slow (or even non-terminating) implementation of a precise type derivation pass;
3. Integration of that pass in the compilation pipeline;
4. (optional) Experiments with strategies to ensure the pass terminates after reasonable computation times.

Proficiency in discrete mathematics, particularly set theory. The student is expected to become familiar with data flow analyses in the course of the project.

The student will learn to apply abstract concepts in the design of a data flow analysis pass for an impure language. They will do so within the limits of a standards-defined language that is not explicitly designed to enable sophisticated static analyses. Finally, they will research and discover strategies to render practically usable a theoretically correct symbolic process.

1. Accumulate a few functions that exhibit register allocation issues;
2. Improve the graph-colouring heuristic by adapting well-known methods;
3. Allocate registers more finely within a single basic block;
4. (optional) Implement a live-range splitting pass;
5. (optional) Exploit register-register exchange instructions to enable SSA-style register allocation.

Basic familiarity with assembly language. Some knowledge of discrete mathematics and of graph theory.

The student will apply sophisticated heuristics to solve an NP-Hard problem. They will also learn to map abstract discrete optimisation concepts to concrete low-level concepts such as architectural registers and assembly instructions, and develop specialised methods that straddle the two views to exploit domain-specific knowledge.

Andrew Appel has some interesting stuff http://www.cs.princeton.edu/~appel/coalesce/.

The allocator is in src/compiler/pack.lisp, and is basically a greedy allocator (now that CMUCL's strange rotating heuristic has been disabled). However, rather than colouring with respect to any well-known ordering heuristic (e.g. the Welsh-Powell decreasing degree order, or Brélaz's dynamic min-degree order), TNs (variables) are ordered for allocation by considering only the loop nesting depth and a cost value.

1. Describe the objective and constraints in the representation selection problem;
2. Reduce the representation selection problem to better understood optimisation problems with efficient heuristics;
3. Improve the currently-existing representation selection heuristic;
4. (optional) Implement value-based representation selection within basic blocks;
5. (optional) Implement SSA-style representation selection, with conversion code at control flow fork/join points.

Basic familiarity with assembly language. Some knowledge of discrete mathematics and of graph theory.

The student will learn to describe a complicated, industrial, combinatorial optimisation problem formally, and to reduce it to classic optimisation problems. They will then have an opportunity to exploit this theoretical basis to improve on an existing heuristic, in practice. Finally, they will be lead to iteratively improve that formal model to better represent the actual problem, while ensuring the existence of efficient solving methods.

1. Determine how to inject ad hoc rewrites during the emission of machine code;
2. Implement a simple, specialised, optimisation using that mechanism;
3. Develop a pattern-definition language appropriate for the chosen rewriting mechanism;
4. Implement some rewrites using that pattern-definition language, and show improvements in some degenerate cases.

Familiarity with assembly language in at least one platform supported by SBCL.

The student will have evaluated how to best extend a system in a direction that was not considered during its initial design. They will also review various approaches to improve code generation at a low level, and create a new domain-specific language that will be used by others. They will finally develop code to detect and improve code at the assembly level.

1. Forward port the interleaved unboxed slot branch;
2. Develop tests for the garbage collector, the interpreter, and the introspection facilities;
3. Determine how to use this new freedom in object layouts;
4. Measure the impact of the changes on the memory usage and on the runtime performance of representative programs.

Some experience with Common Lisp. Familiarity with x86 or x86-64 assembly language is helpful but optional.

The student would become comfortable with data representation issues at a low level, develop and execute tests for a fundamental part of the system, and guide technical decisions with empiric measures from benchmarks that reflect reality. Moreover, this would be done within the constraints specified by a standard.

https://github.com/pkhuong/sbcl/tree/fast-unboxed-struct seemed to be mostly working a couple years ago. There's still a lot of work to adapt introspection code, and then to actually exploit the new freedom in layout.

1. Forward port of a software write barrier branch;
2. Development of unit tests for the garbage collector, particularly for the write barriers;
3. Characterisation of the strengths and weaknesses of software and memory protection write barriers;
4. (optional) Determine how best to use software write barriers in SBCL, e.g. by allowing boxed and unboxed objects to be allocated contiguously, or by enabling huge pages.

Familiarity with x86-64 assembly language.

The student would acquire experience working with compilers and runtime systems at the assembly level, and develop techniques to automatically detect subtle code generation and concurrency bugs. They would also improve their ability to characterise the performance of (a part of) a complex system, and act upon that information to improve such a system.

The were several trees over the past couple years. The latest one is https://github.com/pkhuong/sbcl/tree/card-2012-3. I believe there's some strange failures for tiny card sizes, and I haven't yet ruled out an old bug elsewhere.

1. Microbenchmarks to understand the effect of aliasing and data misalignment when processing large (vector) data;
2. Development of alternative large object allocation and deallocation routines that improve the cache utilisation of SBCL;
3. Development of a block allocation strategy that is better suited to the algorithms and data structures operating systems use to manage ranges of virtual memory;
4. (optional) Identification of further global issues in SBCL's memory management.

Proficiency in C. Basic understanding of computer architecture and of contemporary operating systems.

The student will gain concrete experience at debugging and tuning the performance of a complete system, with interactions between a managed language runtime, the operating system, and the CPU's microarchitecture. In addition to applying concepts from computer architecture and operating systems theory to improve the performance of a runtime system, they will also apply statistical techniques to convincingly exhibit these improvements.

https://github.com/pkhuong/sbcl/tree/discontiguous-unboxed-allocation seemed to mostly work to avoid interleaving pages.

1. Development of a few fixed assertions (e.g. that an objects is dead, or is refered by exactly one heap object) that can be checked asynchronously, during or after major garbage collection cycles;
2. A vistualisation tool to help track references in object graphs, and to better understand the size of data in SBCL's heap;
3. Integration of the assertions in minor GC;
4. (optional) Development of a domain specific language to allow the description of specialised assertions.

Familiarity with manual memory management, and with the manipulation of pointers. Knowledge of graph theory and predicate logic may be useful. Interest in the low end of complexity classes would be an asset.

The student would identify how to respond to the needs expressed by programmers, most likely by taking inspiration from tools described in scientific literature. They would also become proficient at processing large data sets (heaps) with streaming approaches that use little auxiliary storage. Finally, they would gain experience in the design and implementation of domain specific languages: the language will balance the conflicting goals of expressiveness and of efficient execution within very little writable storage.

1. Description of the interface between SBCL's runtime and its memory management subsystem;
2. Implementation of mark-and-sweep in a distinct heap from the current copying one, with eviction from the copying heap to the mark-and-sweep heap;
3. Integration of the mark-and-sweep heap with the copying heap and its data structures;
4. (optional) Adaptation of mark-and-sweep GC to efficiently load images and to save less fragmented images;
5. (optional) Improved performance on read-mostly data.

Knowledge of C and understanding of operating systems internals.

The student will appreciate the challenges faced by the implementations of languages with managed memory. They will understand the theory of classic garbage collection and memory management algorithms, and implement them. They will also develop code that interacts directly with the operating system in order to manage resources efficiently.

A minimal working (?) mark/sweep, plugged in the usual collector at https://github.com/pkhuong/sbcl/tree/foreign-mark-sweep. There's actually very little that must be changed in pre-existing code to get something going.

1. Description of the interface between SBCL's runtime and its memory management subsystem;
2. Stand-alone program that interfaces with MPS and presents challenges similar to that of SBCL (tagged pointers, several types of weaknesses, some data layout described by normal heap objects, ability to load a heap from disk, etc.);
3. Port the stand-alone program's design to SBCL, for a single platform;
4. (optional) Determine which pools are better suited to Common Lisp, and how to expose that choice to users.
5. (optional) Port SBCL/MPS to several platforms.

Knowledge of C and understanding of operating systems internals.

The student will become familiar with the memory management subsystem used in a managed language that supports OS threads, and with the internals of a state of the art garbage collector. They will then gain experience with the integration of independently-developed systems. They will also interface directly with the operating systems as required for the development of a performance-oriented runtime system.