Computer Systems: A Programmer’s Perspective (2nd Edition)

I picked up Computer Systems: A Programmer’s Perspective (2nd Edition) by Randal Bryant and David O’Hallaron while searching for a stimulating book on computer architecture or operating systems. CSAPP turned out to be a good find since it is aimed at the intersection of computer architecture, computers systems and OS. Using practical examples and problems the book walks the student through all the hardware and software knowledge that is required to understand how a program comes to life on a computer.

Assume a student compiles a Hello world program and runs it. A plethora of hardware features and a large set of software come together to make this simple magic possible. Software like compiler, assembler, linker, loader, libraries and operating system kernel help to compile and load the program. Hardware features like hard disk, main memory, controllers, buses, cache and the processor bring the program to life. Also, hardware and software need to also act in tandem in virtual memory, system calls and interrupt handling to make the execution of a program scalable, efficient, fast and safe. This book argues that a good programmer needs to be aware of all the afore mentioned concepts and these are what the book tries to cover.

Some notes about this book:

• The book is structured as a workbook. You read a concept, solve a problem or experiment with a program that illustrates it and then move on to the next concept. There are trivia, blurbs and practical information about IA32 (Intel) architecture and Linux where-ever necessary. This ensures that the book remains grounded in reality and never feels dry to study.
• The authors have tried their best to introduce as many of modern multiprocessor concepts as possible in a practical way. There is a lot missing, for example, super-scalar architecture and out-of-order execution. However, the programmer interested in these details can easily learn about them with a book like Inside The Machine.
• The chapters on memory hierarchy and virtual memory are the real treasure in this book. The sections on cache here and in Inside The Machine stand head-to-head as the most practical introductions to the topic.
• Virtual memory is an important concept, but sadly it gets short shrift in computer science education. This is because it requires the OS and hardware to work together and those subjects are typically covered by two different courses or textbooks in university. Not having to deal with such caste boundaries, this book is able to show the student how virtual memory is brought to life.
• The book gets a bit vague towards the end. I was not interested in and did not see any benefit for this book to touch on areas of system I/O, network programming and concurrency.

I am happy to conclude that CSAPP is a stimulating book to study and work through. This book covers all the knowledge that a good programmer needs to understand how his program executes upon the OS and CPU and how to make it efficient, fast and scalable. I highly recommend Computer Systems: A Programmer’s Perspective for anyone who feel they need a better grasp of these ideas.

Programming Massively Parallel Processors

The next step for a CUDA newbie after CUDA by Example would naturally be the book Programming Massively Parallel Processors by David Kirk and Wen-mei Hwu. They taught the first course on CUDA at UIUC for a few semesters and this book is based on its lecture notes. I had used their lecture notes and videos when I first learnt CUDA.

To write any CUDA application that moulds the problem optimally to the CUDA architecture requires the programmer to think very differently from programming on a CPU. Using a matrix multiplication example, the authors walk the student through many levels of improvement. The authors introduce the different facets of the architecture and end up improving the performance of the solution by as much as two orders of magnitude in the end.

All the concepts of the CUDA architecture are covered: the thread-block-grid hierarchy, the global-shared-local memories and barrier synchronization. Details of the warps and the warp scheduler are explained. Since most CUDA applications are scientific, there is an entire chapter on the floating point format. This chapter gives a practitioner’s perspective that I found to be more useful than the popular but obscure What every computer scientist should know about floating-point arithmetic. There are two chapters on application case studies, which are mostly useless since one cannot understand the application intimately enough to draw any lessons from it.

CUDA runs only on NVIDIA devices. OpenCL is its twin that is designed to be used on all kinds of CPU and GPU processors. The authors have thrown in a chapter on OpenCL for folks who need to transition to it. OpenCL is exactly like CUDA, except that it does not have an equivalent of the CUDA Runtime API. So, the programmer ends up spending some time building the scaffolding required to run his kernels.

Programming Massively Parallel Processors is a easy book to study from. It should be accessible to any intermediate-to-expert programmer. Newbies can check out CUDA by Example before studying this book. I do wish this book covered some information on cache configuration, launch bounds, profiling, compiler options and other intimate details which one ends up using to squeeze out the last bit of performance. Currently, I do need to fall back onto the CUDA Programming Guide for such information. The book is also a wee bit outdated since the Fermi architecture is not well covered and the new Kepler architecture has already been released.

Algorithms (4th Edition)

One of the biggest roadblocks in studying Computer Science is the popular tome Introduction to Algorithms by CLRS. It is the most common textbook for introductory algorithms courses at universities. While it is a great book for learning analysis of algorithms and as a reference, it is a horrible book to learn algorithms. I am pretty sure a great many number of students have been turned off from and have fear of algorithms since this book was their first look at algorithms. Thankfully, there is an excellent cure for this problem.

I recently re-discovered the wonderful world of microprocessors with the book Inside the Machine. It made me realize that there must be books out there on every topic that are more intuitive, stimulating and illustrative than the status quo. I started to look for such a book on algorithms. After checking out almost every textbook on this topic out there, I discovered Algorithms (4th Edition) by Robert Sedgewick and Kevin Wayne. And, I fell in love!

This is an introductory textbook for algorithms. The book covers all the most important algorithms on sorting, searching, graphs and strings. Real-world problems and historical perspectives are provided at the beginning of every chapter to motivate the algorithm. After that a skeleton of a Java class is sketched out with the API that is demanded by the problem. The authors then show why other algorithms studied earlier in the book cannot solve this problem. Using these failings as a key, the user is introduced to a new concept that can solve the problem. This is then advanced to the final algorithm with full working Java code to fill out the skeleton API. Finally, many propositions about the time and space complexity of the algorithm are put forward with their proofs.

I never thought that I would find an Algorithms book so addictive that I would study it cover to cover! What is so special about this book? There are a few reasons for that. First are the illustrations. There are more illustrations in this book than there are pages (yes, unbelievable!). The authors have taken great pains to tear apart the difficulty in understanding how and why an algorithm works. And then the code: this is the simplest, most elegant real code ever written for algorithms. Do red-black trees haunt your dreams? This book banishes that fear by elegantly using 2-3 trees and morphing that understanding to red-black trees. And finally the proofs. Every proposition and its intuitive proof is such a joy to work through and finally understand that it gives one a high!

In my humble opinion, Algorithms (4th Edition) by Sedgewick and Wayne is the best introduction to algorithms. There is quite simply no other book out there that will make you fall in love with algorithms like this one. My only advise is that you make sure you understand every illustration and concept in the book. That goes a long way in giving you an intuitive feel of the algorithm. If you are picking up this book, do remember to check out the book’s website. It contains a lot of supporting content, including code and errata. (I am honored to have been able to contribute quite a few errata there ). The final icing on the cake is that Sedgewick and Wayne will soon be teaching a two-part Algorithms course based off this book at Coursera soon!

Leaf Storm

A copy of One Hundred Years of Solitude sits on my shelf mocking me everytime I look at it. I have tried to read this book by Gabriel Garcia Marquez quite a few times and have given up in the middle. In an effort to break that jinx I read Leaf Storm, a shorter work by the same author. Gabriel Garcia Marquez is a writer from Colombia and is the winner of the 1982 Nobel Prize for Literature. The Picador edition of Leaf Storm I read is translated from Spanish by Gregory Rabassa.

The book takes its name from the novella that appears first in the book, followed by six other short stories. The Leaf Storm walks through the thoughts of three people: an old man, his middle-aged daughter and her small son on a hot noon in the fictional town of Macondo in 1909. (Incidentally, Macondo takes center-stage in One Hundred Years of Solitude too.) The occasion is the demise of the old man’s friend, a doctor, who the whole town despises. As these three people sit in the doctor’s dusty old house preparing his body for burial, they take a long walk through the years of their lives. The works that I was strong reminded of while reading Leaf Storm were those of RK Narayan. While lacking the myriad colorful characters and landmarks of Malgudi, the principal characters, their home, lives and thoughts are similar in flavour to those in RKN’s creations.

In The Handsomest Drowned Man in the World, the body of an adonis washes up at a fishing village. Though very much dead, the charms of his body sets the hearts and minds of the womenfolk aflutter and gives them new dreams while they prepare to bury him. A man with wings lands in the chicken coop of a farmer in A Very Old Man with Enormous Wings. The poor couple use him as an attraction to get rich, but after his sheen fades he is discarded amongst their poultry. Just when they think he is almost dead, he recovers and flies off into the clouds. Blacaman the Good, Vendor of Miracles is a story where a mistreated assistant of a fair trickster gains actual miracle powers and watches his former master kill himself. The Last Voyage of the Ghost Ship is something unique: an entire short story told as one, yes o-n-e long sentence! In Monologue of Isabel Watching It Rain in Macondo returns the reader to the life of Isabel (the daughter from the Leaf Storm novella) to revisit a few days of her pregnancy when it rained non-stop for a week in Macondo. The last story Nabo is about a stablehand who enters into a coma.

Leaf Storm is a comfortable introduction to Gabriel Garcia Marquez. The Leaf Storm novella and Isabel’s Monologue are my favorite picks from this book. These really portray the signature style of Garcia, which I have seen in One Hundred Years. The drowned man and the man with wings are children’s fables, beautifully told. The rest of the stories are just oddities, especially Nabo, which I could not even understand properly. I liked both the story telling style and the settings of Colombia of the early 20th century in Garcia’s stories. Much like RKN and Graham Greene, he does not need grand settings or premises, but revels in the strength of his realistic characters and their small-life travails. It is yet to be seen how I will fare with his serious works like One Hundred Years of Solitude and Autumn of the Patriarch.

Inside the Machine

I find most of the celebrated books on computers to be extremely dry. Though they are packed with important information, they make no effort to engage the reader and fail to give an intuitive understanding of the subject. Jon Stokes is that rare breed of technology writer whose book Inside the Machine is so edge-of-the-seat absorbing that it is hard to believe that it is about computer architecture and microprocessors. Stokes is the co-founder of the Ars Technica website, one of my favorite haunts, where he has written in-depth articles about processors since 1998.

The first 4 chapters of the book deal with the basic architecture and execution steps of a microprocessor, pipelining and superscalar execution. Stokes takes the reader through 4 conceptual views of the CPU: (1) as a calculator (2) as a computer reading instructions and data from memory (3) the programmer’s view of the processor, also known as the Instruction Set Architecture (ISA) and (4) the actual microarchitecture of the chip. In here and in the rest of the book, Stokes uses lots of colorful illustrations to depict how the CPU is structured and how it behaves while processing instructions. Without a doubt, these are the most engrossing diagrams I have seen of computer architecture and they are easy to grasp and remember. Add to this the countless wonderful analogies that Stokes describes in the text that help to see the topic from many different viewpoints.

The rest of the book picks many popular processors and uses each to introduce a contemporary technique or concept. What follows are the items I found interesting in this part of the book. Chapter 5 deals with the Pentium and Pentium Pro (P6) microarchitectures, using them to explain branch prediction, dynamic scheduling and micro-operation decoding. Chapter 6 uses PowerPC processors to talk about RISC and its typical microarchitecture. Chapter 7 introduces the Pentium 4 (NetBurst) microarchitecture whose ginormous 20-stage pipeline I loathed and whose trace cache I thought was a really cool idea. Chapter 8 covers vector support: MMX, SSE and SSE2 in Intel and AltiVec in PowerPC processors. Chapter 9 talks about 64-bit computing, tells the story of Intel’s failure to push a new ISA through the 64-bit Itanium and how AMD stole the show with its x86-64. Chapter 11 is oddly placed towards the end and it deals with caching. Special mention goes to the kick-ass analogies and delightful illustrations of the types of caching and caching hierarchy here. The final Chapter 12 brings the reader to today, with the power-saving architecture of Pentium M and the Core 2 Duo multi-threading architecture.

Inside the Machine is an absolute must-read for anyone who works with computers. I only wish the ARM microarchitecture, which is now popular on handheld devices, was covered in the book. Jon Stokes really succeeds in giving the reader a big-picture view of the internal structure and workings of today’s microprocessors. Do not be surprised if this book turns you into a processor geek who follows the microarchitectures of upcoming processors. Inside the Machine is the kind of book on science and technology that I love to read and cherish.

Steve Jobs

If I close my eyes and picture Steve Jobs, it is always him wearing a black turtleneck, doing a reality distorting pitch to unveil a revolutionary new Apple product. But, who is Jobs really? How does he create such exquisite products? How does he manage time and get things done? How is he as family, boss and a human being? It is for such questions that I was interested in his biography. The biography of Steve Jobs is written by Walter Isaacson and was released soon after his demise. I picked up the book after learning that the ultra-secretive Jobs had done a tell-all in the book and it would be balanced in covering both his great and not-so-great traits.

Jobs was a genius and visionary. If not for him, the world of computers, software and gadgets would be much less beautiful or useful. With the Apple II, the iPod and the iPhone, he created products which had been envisioned before, but had not been created with such detail and simplicity. He had an unwavering focus on how his products looked, felt and were experienced. Everything had to be just right: the shape, color, texture and weight. At Apple he created a culture where design drove engineering. He was a pathfinder, understanding what users wanted without having to rely on user studies, but instead on his legendary intuition and taste.

Despite having created some of the most popular digital products ever, Jobs used old-world habits and tools for his creation. He regularly took long walks to think and to talk about ideas. He used sketchbooks all his life to write, draw and thrash out ideas. In his team meetings, he insisted on using whiteboards to formulate and simplify thoughts. He believed that sparks and ideas were formed when random interactions happened between people and he built workplaces that encouraged this. He delivered products on time by resolving issues by meeting or calling people immediately, instead of email.

Jobs was also extremely hard to work with. He was highly opinionated, judging anyone or anything as either great or crap, even if he had no idea about the subject. A lot of his friends, partners and employees left him, not being able to bear his mercurial attitude. All his life, he regularly screamed at and insulted people whose work he did not like. He was a hard dictator, never interested in working for or with others, his orders had to be followed. With his authoritarian style of management he drove away all leaders and independent thinkers from his organization. He routinely lied and took credit for ideas of his employees. Despite being an excellent judge of human taste, it remains a mystery why he treated his fellow humans so badly. Isaacson attributes this to him being abandoned by his biological parents. But, that does not really explain why he did not accept his own daughter Lisa for more than a decade.

From his college days, Jobs was deeply influenced by Eastern spirituality, philosophy and habits. He took to veganism and followed it all his life. He also practiced weird diets of fruits and juices. Even after being diagnosed with cancer he did not undergo surgery, but instead went for quack medicines. His stubbornness in sticking to his belief despite all evidence to the contrary ultimately led to his early demise.

I recommend picking up this book to examine the greatness and the failings of Steve Jobs. Every reader is sure to benefit from the lessons of his life.

Version Control by Example

Look what arrived in my snail-mail last weekend: a free dead-tree copy of Version Control by Example written by Eric Sink! I know Eric Sink from his Source Control HOWTO, a series of fantastic introductory posts on the subject. In this book, Eric Sink gives a simple introduction to version control systems (VCS), the common operations in a VCS and he illustrates these operations in Subversion, Mercurial, Git and Veracity. The book ends with chapters that dip into the internal workings of distributed VCS (DVCS), common workflows of using DVCS and best practices.

Eric Sink is a delightful writer with the talent to make technology accessible and fun. (He reminds me of Tanenbaum, whose textbooks I love for the same reason.) I especially loved his analogy of VCS to a multi-threaded program, which he uses all through the book. Before getting into examples, he provides a solid debate on the pros and cons of centralized VCS (CVCS) vs. DVCS. After that, he shows a sample workflow between two programmers, one in the USA and other in UK, who have to collaborate on the code of a game using a VCS. He uses this scenario four times, once for each VCS he illustrates in the book. I used to use Subversion for my personal work before and my current life completely revolves around Mercurial. So, I loved going through the chapters on these VCS, it acted as a good revision. I skipped the chapter on Git, after seeing (yet again) how it makes every action more complicated than necessary. The final tool is Veracity, an open-source DVCS created by SourceGear which is Eric Sink’s company. It adds some extra features needed by commercial users that are not provided in most free DVCS.

Version Control by Example is a super-fast read. It is a practical book, there is nothing to mull or chew over here. If you are either thinking about using a VCS (oh, you must!) or thinking about switching from a CVCS to a DVCS, please pick up this book. The dead-tree version has gaudy page design and is printed on glossy paper. But, once you get over these distractions, the content is good. The book is also available online here.

Windows Sysinternals Administrator’s Reference

I have been a huge fan of the Sysinternals tools ever since I switched to Windows for my work. These tools give the ability to peek into every heartbeat of Windows, and you develop an appreciation for the beauty and complexity of this operating system. So, it is no wonder that I eagerly awaited the Windows Sysinternals Administrator’s Reference once Mark Russinovich announced it earlier this year. Written by Mark and Aaron Margosis, this book helps readers use the Sysinternals tools effectively to understand the working internals of Windows, and to diagnose and fix problems.

Part 1 talks about the history of Sysinternals tools and gives a brief description of administrator privileges, user-kernel mode, processes, threads, jobs and handles in Windows. Though designed similar to other operating systems, Windows is a different beast. This chapter is a highly educational read to understand just how it differs and to catch up on the Windows OS jargon. The first 3 chapters of Part 2 are worth the price of the book itself — they go deep into the capabilities of Process Explorer, Process Monitor and Autoruns. Having learnt these 3 tools one can start to live comfortably with Windows. (Well, almost!) The rest of Part 2 covers the other Sysinternals tools, most of which I do not use. Part 3 is a compendium of many troubleshooting mystery cases, which were solved by using Sysinternals tools. Followers of Russinovich’s blog or talks will be familiar with most of these since he has written and presented about them before. Written like a detective mystery, each of these are sure to be engaging to geeks.

Windows Sysinternals Administrator’s Reference is a good companion to the Windows Internals books, providing the much needed practical information and tools to get down-and-dirty with the internals of Windows. Like his blog and talks, Russinovich’s narrative here is entertaining and educational to read. The book completely pays for itself with just Part 1 and the first 3 chapters of Part 2. This book is a must for everyone who uses Windows as their primary operating system.