In our CS1 course, we found that students were failing at a rate similar to that reported in literature. In an effort to improve this DFW rate, we made a few changes to the course. While the changes led to some improvement, the results were not as significant as we expected. We found that in our CS1 course, first-semester students were passing at a significantly higher rate than non-first-semester students. Upon looking at other STEM and non-STEM courses at the university, we noted that the institution's first term calculus and introductory English courses had similar patterns, however the introductory sociology course did not. Further data analyses challenged several other of our beliefs about who was failing the course. Our findings leave us with several questions. Is this pattern specific to our university? Is this a particular course problem? From the perspective of the discipline, is there something in this data that points to a set of problems for computing education researchers to consider? This poster serves as both a presentation of our initial experiential results and an attempt to start a conversation amongst community members around whom actually is struggling within our early CS courses.

Instructors of the introductory computer science courses, commonly called "CS1" and "CS2", face a large number of choices when designing their classes. Instructors have available to them a multitude of ways to explain each topic as well as course-wide choices such as objects-first or objects-late or using a functional or procedural language. Understanding how these options can affect student learning would help simplify these decisions. Unfortunately, just comparing how well students perform may not be accurate as it ignores the many confounding factors that could also have made a difference. To get beyond that problem, this study investigates underlying factors that affect student learning. Using a survey of instructors, we find that students' abilities are nearly always correlated with the importance that the instructor placed on a particular topic. Our results also highlight several "hard" topics for which student mastery and topic importance were not correlated in CS1 and only weakly correlated in CS2. While one might expect the time spent covering a topic in class to also be correlated with student mastery, we find little evidence of this. In fact, for some basic programming concepts, we document negative correlations between instructional time and learning. We discuss how instructors can use these results when organizing their courses and how the computer science education community can use this finding of "hard" topics to focus their efforts.

Students in introductory programming courses struggle with building the mental models that correctly describe concepts such as variables, subroutine calls, and dynamic memory usage. This struggle leads to lowered student learning outcomes and, it has been argued, the high failure and dropout rates commonly seen in these courses. We will show that accurately modeling what is occurring in memory and requiring students to trace code using this model improves student performance and increases retention. This paper presents the results of an experiment in which introductory programming courses were organized around code tracing. We present program memory traces, a new approach for tracing code that models what occurs in memory as a program executes. We use these traces to drive our lectures and to act as key pieces of our active learning activities. We report the results of student surveys showing that instructor tracing was rated as the most valuable piece of the course and students' overwhelming agreement on the importance of the tracing activities for their learning. Finally, we demonstrate that trace-based teaching led to statistically significant improvements student grades, decreased drop and failure rates, and an improvement in students' programming abilities.

Automatically-tested online programming exercises can be useful in introductory programming courses as self-tests to accompany readings, for in-class assessment, for skills development, and to provide additional practice for students who need it. CloudCoder (http://cloudcoder.org) is an effort to build a community based on an open-source programming exercise system (currently supporting C, Java, and Python) tightly integrated with a repository of freely-redistributable programming exercises written and used by members of the community. The goal of the project is to make programming exercises easy and free to incorporate into any programming course.

To achieve optimal performance, garbage-collected applications must balance the sizes of their heaps dynamically. Sizing the heap too small can reduce throughput by increasing the number of garbage collections that must be performed. Too large a heap, however, can cause the system to page and drag down the overall throughput. In today's multicore, multiprocessor machines, multiple garbage-collected applications may run simultaneously. As a result, each virtual machine (VM) must adjust its memory demands to reflect not only the behavior of the application it is running, but also the behavior of the peer applications running on the system.

Thirty-one years ago, the ACM Computing Curricula used the terms "CS1" and "CS2" to designate the first two two courses in the introductory sequence of a computer science major. While computer science education has greatly changed since that time, we still refer to introduction to programming courses as CS1 and basic data structures courses as CS2. This common shorthand is then used to enable students to transfer between institutions and as a base of many research studies.

Pretenuring can reduce copying costs in garbage collectors by allocating long-lived objects into regions that the garbage collector will rarely, if ever, collect. We extend previous work on pretenuring as follows: (1) We produce pretenuring advice that is neutral with respect to the garbage collector algorithm and configuration. We thus can and do combine advice from different applications. We find for our benchmarks that predictions using object lifetimes at each allocation site in Java programs are accurate, which simplifies the pretenuring implementation. (2) We gather and apply advice to both applications and Jikes RVM, a compiler and runtime system for Java written in Java. Our results demonstrate that building combined advice into Jikes RVM from different application executions improves performance, regardless of the application Jikes RVM is compiling and executing. This build-time advice thus gives user applications some benefits of pretenuring, without any application profiling. No previous work uses profile feedback to pretenure in the runtime system. (3) We find that application-only advice also consistently improves performance, but that the combination of build-time and application-specific advice is almost always noticeably better. (4) Our same advice improves the performance of generational, Older First, and Beltway collectors, illustrating that it is collector neutral . (5) We include an immortal allocation space in addition to a nursery and older generation, and show that pretenuring to immortal space has substantial benefit.

Most application's performance is impacted by the amount of available memory. In a traditional application, which has a fixed working set size, increasing memory has a beneficial effect up until the application's working set is met. In the presence of garbage collection this relationship becomes more complex. While increasing the size of the program's heap reduces the frequency of collections, collecting a heap with memory paged to the backing store is very expensive. We first demonstrate the presence of an optimal heap size for a number of applications running on a machine with a specific configuration. We then introduce a scheme which adaptively finds this good heap size. In this scheme, we track the memory usage and number of page faults at a program's phase boundaries. Using this information, the system selects the soft heap size. By adapting itself dynamically, our scheme is independent of the underlying main memory size, code optimizations, and garbage collection algorithm. We present several experiments on real applications to show the effectiveness of our approach. Our results show that program-level heap control provides up to a factor of 7.8 overall speedup versus using the best possible fixed heap size controlled by the virtual machine on identical garbage collectors.

Programmers are writing a rapidly growing number of programs in object-oriented languages, such as Java and C#, that require garbage collection. Garbage collection traces and simulation speed up research by enabling deeper understandings of object lifetime behavior and quick exploration and design of new garbage collection algorithms. When generating perfect traces, the brute-force method of computing object lifetimes requires a whole-heap garbage collection at every potential collection point in the program. Because this process is prohibitively expensive, researchers often use granulated traces by collecting only periodically, for example, every 32 KB of allocation.We extend the state of the art for simulating garbage collection algorithms in two ways. First, we develop a systematic methodology for simulation studies of copying garbage collection and present results showing the effects of trace granularity on these simulations. We show that trace granularity often distorts simulated garbage collection results compared with perfect traces. Second, we present and measure the performance of a new algorithm called Merlin for computing object lifetimes. Merlin timestamps objects and later uses the timestamps of dead objects to reconstruct when they died. The Merlin algorithm piggybacks on garbage collections performed by the base system. Experimental results show that Merlin can generate traces over two orders of magnitude faster than the brute-force method which collects after every object allocation. We also use Merlin to produce visualizations of heap behavior that expose new object lifetime behaviors.

Garbage collection yields numerous software engineering benefits, but its quantitative impact on performance remains elusive. One can compare the cost of conservative garbage collection to explicit memory management in C/C++ programs by linking in an appropriate collector. This kind of direct comparison is not possible for languages designed for garbage collection (e.g., Java), because programs in these languages naturally do not contain calls to free. Thus, the actual gap between the time and space performance of explicit memory management and precise, copying garbage collection remains unknown.We introduce a novel experimental methodology that lets us quantify the performance of precise garbage collection versus explicit memory management. Our system allows us to treat unaltered Java programs as if they used explicit memory management by relying on oracles to insert calls to free. These oracles are generated from profile information gathered in earlier application runs. By executing inside an architecturally-detailed simulator, this "oracular" memory manager eliminates the effects of consulting an oracle while measuring the costs of calling malloc and free. We evaluate two different oracles: a liveness-based oracle that aggressively frees objects immediately after their last use, and a reachability-based oracle that conservatively frees objects just after they are last reachable. These oracles span the range of possible placement of explicit deallocation calls.We compare explicit memory management to both copying and non-copying garbage collectors across a range of benchmarks using the oracular memory manager, and present real (non-simulated) runs that lend further validity to our results. These results quantify the time-space tradeoff of garbage collection: with five times as much memory, an Appel-style generational collector with a non-copying mature space matches the performance of reachability-based explicit memory management. With only three times as much memory, the collector runs on average 17% slower than explicit memory management. However, with only twice as much memory, garbage collection degrades performance by nearly 70%. When physical memory is scarce, paging causes garbage collection to run an order of magnitude slower than explicit memory management.

Heap size has a huge impact on the performance of garbage collected applications. A heap that barely meets the application's needs causes excessive GC overhead, while a heap that exceeds physical memory induces paging. Choosing the best heap size a priori is impossible in multiprogrammed environments, where physical memory allocations to processes change constantly. We present an automatic heap-sizing algorithm applicable to different garbage collectors with only modest changes. It relies on an analytical model and on detailed information from the virtual memory manager. The model characterizes the relation between collection algorithm, heap size, and footprint. The virtual memory manager tracks recent reference behavior, reporting the current footprint and allocation to the collector. The collector uses those values as inputs to its model to compute a heap size that maximizes throughput while minimizing paging. We show that our adaptive heap sizing algorithm can substantially reduce running time over fixed-sized heaps.

We introduce a new family of connectivity-based garbage collectors (Cbgc) that are based on potential object-connectivity properties. The key feature of these collectors is that the placement of objects into partitions is determined by performing one of several forms of connectivity analyses on the program. This enables partial garbage collections, as in generational collectors, but without the need for any write barrier.The contributions of this paper are 1) a novel family of garbage collection algorithms based on object connectivity; 2) a detailed description of an instance of this family; and 3) an empirical evaluation of Cbgc using simulations. Simulations help explore a broad range of possibilities for Cbgc, ranging from simplistic ones that determine connectivity based on type information to oracular ones that use run-time information to determine connectivity. Our experiments with the oracular Cbgc configurations give an indication of the potential for Cbgc and also identify weaknesses in the realistic configurations. We found that even the simplistic implementations beat state-of-the-art generational collectors with respect to some metrics (pause times and memory footprint).

Programmers are writing a large and rapidly growing number of programs in object-oriented languages such as Java that require garbage collection (GC). To explore the design and evaluation of GC algorithms quickly, researchers are using simulation based on traces of object allocation and lifetime behavior. The brute force method generates perfect traces using a whole-heap GC at every potential GC point in the program. Because this process is prohibitively expensive, researchers often use granulated traces by collecting only periodically, e.g., every 32K bytes of allocation.We extend the state of the art for simulating GC algorithms in two ways. First, we present a systematic methodology and results on the effects of trace granularity for a variety of copying GC algorithms. We show that trace granularity often distorts GC performance results compared with perfect traces, and that some GC algorithms are more sensitive to this effect than others. Second, we introduce and measure the performance of a new precise algorithm for generating GC traces which is over 800 times faster than the brute force method. Our algorithm, called Merlin, frequently timestamps objects and later uses the timestamps of dead objects to reconstruct precisely when they died. It performs only periodic garbage collections and achieves high accuracy at low cost, eliminating any reason to use granulated traces.

Pretenuring can reduce copying costs in garbage collectors by allocating long-lived objects into regions that the garbage collector with rarely, if ever, collect. We extend previous work on pretenuring as follows. (1) We produce pretenuring advice that is neutral with respect to the garbage collector algorithm and configuration. We thus can and do combine advice from different applications. We find that predictions using object lifetimes at each allocation site in Java prgroams are accurate, which simplifies the pretenuring implementation. (2) We gather and apply advice to applications and the Jalapeño JVM, a compiler and run-time system for Java written in Java. Our results demonstrate that building combined advice into Jalapeño from different application executions improves performance regardless of the application Jalapeño is compiling and executing. This build-time advice thus gives user applications some benefits of pretenuring without any application profiling. No previous work pretenures in the run-time system. (3) We find that application-only advice also improves performance, but that the combination of build-time and application-specific advice is almost always noticeably better. (4) Our same advice improves the performance of generational and Older First colleciton, illustrating that it is collector neutral.