Due: Thursday, 15 November 2018
Part I: Memory Management in C
This part is to try and estimate the big O complexity and time cost of memory management in C. There are two main questions.
- What is the average time per call to allocate a certain
amount of memory?
Try timing several hundred/thousand calls to make the estimate, and try the experiment with at least three different memory sizes (small, medium, large).
- Does the time of a memory management call change with the
number of allocation and free operations the program has
You can test this by writing a program that makes lots of both types of actions and timing either one call (which might be hard), or timing a few hundred calls (which is probably easier) over a period of time.
See if it makes a difference when you allocate/free the same size memory space versus many different sized memory spaces.
There are many ways to time code. One is to use the ftime library call, which returns a time stamp you can use to estimate total run time reasonably well. Don't try to use it to time small things. But it works ok to use for stuff that takes at least a quarter-second.
The second way to time code is to use a profiler. On a linux machine, you can use a tool called gprof. You can use gprof on any of the dwarves in the robotics lab.
Part II: Memory Management in Selected Languages
This part is to do some research on memory management in your two languages.
- Do your best to research what memory management algorithms
your languages use. For example, does it use reference
counting, mark-sweep, copy collection, or some combination of
- If your language has explicit allocation/deallocation, then create some code examples.
- If your language requires allocation, but not deallocation, then create some code examples. Show some side-by-side comparisons of the differences between C and your language.
- If your language pretty much hides memory allocation, show a variety of statements that create memory, and a variety of conditions whereby that memory gets lost (or put back into a free memory pool).
- Undertake an experiment in a language with automatic memory management (or Java, if neither of your languages fits the model), and see if you can identify when a garbage collection sweep takes place. Create and delete lots of memory inside a function and time the function as you call it many times. Look for times when the function call takes significantly more time than average. See if you can write a program that automatically detects garbage collections from the timing information.
- Describe memory management for a third language.
- For the memory management example, try writing a functionally equivalent example in C, explicitly handling the kinds of information required for the memory management system of your chosen language.
- Look up the code for malloc and free in glibc and explain how they work in your wiki report.
- Write a compilable haiku on memory management.
- Use a profiler to test your code.
- Use valgrind to test your C data structures from prior projects and show that they do not leak memory (fix them if they do).
- Explore how to do reference counting properly when writing C code to interface with Python. If you want to try writing code, use the ctypes package in Python to connect to C functions.
The submission of this project has three components:
- Code: The source code for the memory management in C and the selected languages should be submitted to the fileserver along with code for any extensions. Please make the filenames of your source code meaningful.Note that the quality of your comments counts toward your grade.
- README: Submit a README file to the fileserver for your C code and the code for your selected languages. The README file can be a .txt file. No matter what, it should be readable from the terminal (no Word or pdf files). It should be well-organized such that readers can easily understand the usage and the outputs of the C code and the code for your selected languages. In addition, any known bugs should be in the README file. Follow the format and content instructions from the writing guide.
- Wiki Report: The non-C language pages for this
project should have the following elements.
- Title of the project and your name. Include your partner's name if you worked with someone for the non-C tasks.
- A section for each task of part II. Each section should contain appropriate snippets of your sample programs, the outputs, and your explanations. Write these as tutorials for other students in the class. Aim for the right level of detail, and define anything that may not be clear. Presenting examples without explanation is insufficient.
- If you complete extensions in your selected languages, please include a section for each extension, providing sample programs, outputs, and explanations. Be sure to indicate credit, if necessary.
Please note that it is your responsibility to explicitly indicate the extensions you have undertaken. If you complete extensions for the C tasks, please indicate that explicitly in the code and README file. If you complete an extension in a selected language, please indicate this explicitly in your wiki report. Along with each extension, indicate if you completed it with a partner.