User loginNavigation |
ImplementationSimon Peyton Jones elected into the Royal Society FellowshipSimon Peyton Jones has been elected as a Fellow of the Royal Society. The Royal Society biography reads:
Congratulations SPJ! By Ohad Kammar at 2016-04-30 19:44 | Functional | General | Implementation | Paradigms | Semantics | Software Engineering | Spotlight | Teaching & Learning | Theory | 4 comments | other blogs | 64102 reads
Performance Problems You Can Fix: A Dynamic Analysis of Memoization OpportunitiesPerformance Problems You Can Fix: A Dynamic Analysis of Memoization Opportunities Performance bugs are a prevalent problem and recent research proposes various techniques to identify such bugs. This paper addresses a kind of performance problem that often is easy to address but difficult to identify: redundant computations that may be avoided by reusing already computed results for particular inputs, a technique called memoization. To help developers find and use memoization opportunities, we present MemoizeIt, a dynamic analysis that identifies methods that repeatedly perform the same computation. The key idea is to compare inputs and outputs of method calls in a scalable yet precise way. To avoid the overhead of comparing objects at all method invocations in detail, MemoizeIt first compares objects without following any references and iteratively increases the depth of exploration while shrinking the set of considered methods. After each iteration, the approach ignores methods that cannot benefit from memoization, allowing it to analyze calls to the remaining methods in more detail. For every memoization opportunity that MemoizeIt detects, it provides hints on how to implement memoization, making it easy for the developer to fix the performance issue. Applying MemoizeIt to eleven real-world Java programs reveals nine profitable memoization opportunities, most of which are missed by traditional CPU time profilers, conservative compiler optimizations, and other existing approaches for finding performance bugs. Adding memoization as proposed by MemoizeIt leads to statistically significant speedups by factors between 1.04x and 12.93x. This paper was recommended by Asumu Takikawa. It is a nice idea, which seems surprisingly effective. The examples they analysed (sadly they don't really explain how they picked the program to study) have a mix of memoization opportunities in fairly different parts of the codebase. There are several examples of what we could call "peripheral communication logic", eg. date formatting stuff, which we could assume is not studied really closely by the programmers focusing more on the problem-domain logic. But there is also an interesting of subtle domain-specific memoization opportunity: an existing cache was over-pessimistic and would reset itself at times where it was in fact not necessary, and this observation corresponds to a non-trivial program invariant. The authors apparently had some difficulties finding program inputs to exercise profiling. Programs should more often be distributed with "performance-representative inputs", not just functionality-testing inputs. In one example of a linting tool, the provided "standard test" was to feed the code of the linting tool to itself. But this was under a default configuration for which the tools' developers had already fixed all alarms, so the alarm-creating code (which actually had an optimization opportunity) was never exercised by this proposed input. Note that the caching performed is very lightweight, usually not a full tabulation of the function. Most examples just add a static variable to cache the last (input, output) pair, which is only useful when the same input is typically called several times in a row, but costs very little space. Compilers as AssistantsDesigners of Elm want their compiler to produce friendly error messages. They show some examples of helpful error messages from their newer compiler on the blog post.
By bashyal at 2015-11-20 05:11 | Functional | Implementation | 68 comments | other blogs | 34398 reads
Optimizing Closures in O(0) timeOptimizing Closures in O(0) time, by Andrew W. Keep, Alex Hearn, R. Kent Dybvig:
Looks like a nice and simple set of optimizations for probably the most widely deployed closure representation. By naasking at 2015-10-04 17:46 | Functional | Implementation | login or register to post comments | other blogs | 30728 reads
Xavier Leroy will receive the Royal Society's 2016 Milner AwardThe Royal Society will award Xavier Leroy the Milner Award 2016
Xavier's replied:
By Ohad Kammar at 2015-09-18 14:48 | Functional | General | Implementation | Object-Functional | OOP | 2 comments | other blogs | 23417 reads
Reagents: Expressing and Composing Fine-grained ConcurrencyReagents: Expressing and Composing Fine-grained Concurrency, by Aaron Turon:
This is a pretty neat approach to writing concurrent code, which lies somewhere between manually implementing low-level concurrent algorithms and STM. Concurrent algorithms are expressed and composed semi-naively, and Reagents automates the retries for you in case of thread interference (for transient failure of CAS updates), or they block waiting for input from another thread (in case of permanent failure where no input is available). The core seems to be k-CAS with synchronous communication between threads to coordinate reactions on shared state. The properties seem rather nice, as Aaron describes:
The benchmarks in section 6 look promising. This appears to be work towards Aaron's thesis which provides many more details. By naasking at 2015-08-24 23:05 | Functional | Implementation | Object-Functional | 2 comments | other blogs | 22030 reads
STABILIZER : Statistically Sound Performance EvaluationMy colleague Mike Rainey described this paper as one of the nicest he's read in a while.
STABILIZER : Statistically Sound Performance Evaluation
One take-away of the paper is the following technique for validation: they verify, empirically, that their randomization technique results in a gaussian distribution of execution time. This does not guarantee that they found all the source of measurement noise, but it guarantees that the source of noise they handled are properly randomized, and that their effect can be reasoned about rigorously using the usual tools of statisticians. Having a gaussian distribution gives you much more than just "hey, taking the average over these runs makes you resilient to {weird hardward effect blah}", it lets you compute p-values and in general use statistics. mbeddr: an Extensible C-based Programming Language and IDE for Embedded SystemsMarkus Voelter, Bernd Kolb1, Daniel Ratiu, and Bernhard Schaetz, "mbeddr: an Extensible C-based Programming Language and IDE for Embedded Systems", SplashCON/Wavefront 2012. Although embedded systems are an increasingly large part of our lives, and despite the fact that embedded software would undoubtedly benefit from the kind safety guarantees provided by more advanced type systems, most embedded software development is still done in C. That's partly a result of toolchain availability, and partly because many more advanced languages typically impose requirements on memory, dynamic memory allocation, and other runtime infrastructure that simply aren't supportable on a lot of resource-constrained microcontrollers or acceptable in a risk-averse environment. Mbeddr seems to be seeking a middle ground between C, and creating a whole new language. From the paper:
It appears that mbeddr allows multiple DSLs to be built on top of C to provide greater safety and more domain-specific expressions of typical embedded software patterns. Additionally, it provides integration with various analysis tools including model-checkers. Another paper, "Preliminary Experience of using mbeddr for Developing Embedded Software", provides a look at how all of these things fit together in use. The mbeddr approach seems similar in concept to Ivory and Tower, although mbeddr uses JetBrains MPS as the platform for creating DSLs instead of building an embedded DSL in Haskell. By Allan McInnes at 2015-07-24 16:47 | DSL | Implementation | Software Engineering | 3 comments | other blogs | 12492 reads
Don Syme receives a medal for F#Don Syme receives the Royal Academy of Engineering's Silver Medal for his work on F#. The citation reads:
Congratulations! By Ohad Kammar at 2015-07-03 19:16 | Cross language runtimes | Fun | Functional | General | Implementation | Object-Functional | OOP | Paradigms | Software Engineering | 5 comments | other blogs | 19043 reads
Draining the Swamp: Micro Virtual Machines as Solid Foundation for Language Development
Draining the Swamp: Micro Virtual Machines as Solid Foundation for Language Development Many of today's programming languages are broken. Poor performance, lack of features and hard-to-reason-about semantics can cost dearly in software maintenance and inefficient execution. The problem is only getting worse with programming languages proliferating and hardware becoming more complicated. An important reason for this brokenness is that much of language design is implementation-driven. The difficulties in implementation and insufficient understanding of concepts bake bad designs into the language itself. Concurrency, architectural details and garbage collection are three fundamental concerns that contribute much to the complexities of implementing managed languages. We propose the micro virtual machine, a thin abstraction designed specifically to relieve implementers of managed languages of the most fundamental implementation challenges that currently impede good design. The micro virtual machine targets abstractions over memory (garbage collection), architecture (compiler backend), and concurrency. We motivate the micro virtual machine and give an account of the design and initial experience of a concrete instance, which we call Mu, built over a two year period. Our goal is to remove an important barrier to performant and semantically sound managed language design and implementation.Inside you will find the specification of an LLVM-inspired virtual instruction set with a memory model (enables proper GC support) including a specification of concurrent weak-memory operations (reusing C(++)11, a debatable choice), relatively rich control-flow primitive (complete stack capture enabling coroutines or JIT-style de-optimization), and live code update. By gasche at 2015-05-17 21:46 | Cross language runtimes | Implementation | 13 comments | other blogs | 30298 reads
|
Browse archives
Active forum topics |
Recent comments
16 weeks 5 days ago
16 weeks 6 days ago
16 weeks 6 days ago
39 weeks 7 hours ago
43 weeks 2 days ago
44 weeks 6 days ago
44 weeks 6 days ago
47 weeks 4 days ago
1 year 15 hours ago
1 year 17 hours ago