Description:

Within the course of Efficient software you will get familiar with the area of software and algorithm optimization under limited resources. The course is focused on the efficient usage of modern hardware architectures - multi-core and multi-processor systems with shared memory. Students will practically implmenet and use presented techniques in C and Java. Main topics are: code optimization, effective data structures and processor cache usage, data structures in multi-threaded applications and implementation of efficient network servers.

Contents:

1. Introduction, modern computer architecture, C compilers.
2. Bentley's rules, C compiler, profiling.
3. Benchmarking, measurements, metrics, statistics, WCET, timestamping.
4. Scalable synchronization ? from mutexes to RCU (read-copy-update), transactional memory, scalable API.
5. Memory access ? efficient programming with caches, dynamic memory allocation (malloc, NUMA, ...)
6. Serialization of data structures ? JSON, XML, protobufs, AVRO, cap'n'proto, mmap/shared memory.
7. Program run ? virtual machine, byte-code, Java compiler, JIT compiler, relation to machine code, byte-code analysis, dissasembly of Java byte-code, optimization in compilers, program performance analysis, profiling.
8. Data concurrency in JVM ? multi-threaded access to data, locks monitoring, atomic operations, lock-less/block-free data structures, non-blocking algorithms (queue, stack, set, dictionary), data races, synchronization.
9. Efficient servers, C10K, non-blocking I/O, efficient networking, threads.
10. JVM ? Memory analysis (dynamic/static), data structures, collections for performance.
11. JVM ? Object allocation, bloom filters, references, effective caching.
12. Virtualization (IOMMU, SR-IOV, PCI pass-through, virtio, ?).
13. Memory Management in JVM ? Memory Layout, Garbage Collectors.

Recommended literature:

[1] MIT: Performance-engineering-of-software-systems
[2] Oaks, S.: Java Performance: 2nd Edition. O'Reilly, USA 2020.
[3] Jones, R., Hosking, A., Moss, E.: The Garbage Collection Handbook - The Art of Automatic Memory Management. CRC Press, USA 2012.
[4] Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming. Morgan Kaufman, 2008.
[5] Fog, A.: The microarchitecture of Intel, AMD and VIA CPU, 2016.
[6] Drepper U.: What every programmer should know about memory, 2007
[7] Jain, R.: The Art of Computer Systems Performance Evaluation. Wiley, New York 1991. (slides, book)
[8] Lilja, D. J.: Measuring Computer Performance: A Practitioner?s Guide. Cambridge University Press, 2000. (book web site, Supplemental Teaching Materials)

Abbreviations used:

Semester:

• W ... winter semester (usually October - February)
• S ... spring semester (usually March - June)
• W,S ... both semesters

Mode of completion of the course:

• A ... Assessment (no grade is given to this course but credits are awarded. You will receive only P (Passed) of F (Failed) and number of credits)
• GA ... Graded Assessment (a grade is awarded for this course)
• EX ... Examination (a grade is awarded for this course)
• A, EX ... Examination (the award of Assessment is a precondition for taking the Examination in the given subject, a grade is awarded for this course)

Weekly load (hours per week):

• P ... lecture
• C ... seminar
• L ... laboratory
• R ... proseminar
• S ... seminar