Install Theme

# starchy thoughts

things learned and hopefully understood

## Interrupts and Exceptions

### 06.17.2013

An interrupt signals the occurrence of an event the kernel should be aware of. Hardware can trigger an interrupt at any time by sending a signal to the CPU, usually through the system bus; software can trigger an interrupt by executing a system call (also called a monitor call). When an interrupt occurs, the CPU stops what it is doing and transfers execution to a fixed location, which usually contains the starting address where the service routine for the interrupt is located. After the routine finishes, the CPU resumes what was interrupted.

Interrupts are an important part of a computer’s architecture. They transfer control to the appropriate interrupt service routine, which is usually defined in an interrupt vector, or array holding the addresses of interrupt service routines for various devices. Modern operating systems are interrupt driven, and events are almost always signaled by the occurrence of an interrupt or a trap.

A trap, or an exception, is a software-generated interrupt caused either by an error (division by zero, segmentation fault, etc.) or by a request from the user program for an operating system service.

In x86, the IDT (interrupt descriptor table) provides pointers to interrupt and exception routines.

## Operating Systems Introduction

### 06.17.2013

An operating system is software that manages the computer hardware and provides common services to user programs. They provide an environment in which a user can easily interface with the computer. Operating systems vary widely and often have different goals (mainframe operating systems versus PC operating systems versus real-time…).

computer system can be divided into the hardware, the operating system, the application programs, and the users. The hardware (CPU, memory, I/O devices) provides basic computing resources. The application programs uses those resources to solve users’ computing problems. The operating system coordinates the use of resources.

A general-purpose computer system usually consists of one or more CPUs and a number of device controllers connected through a common bus that provides access to shared memory. The CPU and device controllers can execute concurrently - thus, a memory controller is provided to ensure orderly access to the shared memory.

A computer must have a bootstrap program, an initial program to run when the computer is powered up or rebooted. This firmware is typically stored in ROM (read-only memory) or EEPROM (electrically erasable programmable read-only memory). It initializes the system - CPU registers, device controllers, memory contents, etc. It also locates and loads the operating system kernel, which is the main component of the operating system.

## MVC Overview

### 06.17.2013

The basic premise of MVC is to separate your objects into three “camps” - the model camp, controller camp, or the view camp.

• controller - how the model is presented to the user (controls how the model is presented in the UI)
• view - objects the controller uses to do what it does

These camps are all separate…so how do they communicate?

• controller -> model (since the controller is responsible for getting the model onscreen)
• controller -> view (since the controller uses the views by communicating through outlets to display the model)

The model and the view never communicate. The model is completely UI independent, so it shouldn’t have to talk to the view. The view should be as generic as possible (emphasis on reusability), so it shouldn’t have to talk to the model, which also greatly simplifies keeping track of everything.

The view can communicate with the controller, but it must be blind (can’t know what class of object it’s talking to), and well-structured. An example of well-structured communication is target-action, where the controller hands an action to an object in the view, and the view sends the action back to a target in the controller when something happens (e.g. button press).

Another example is delegation, when the view and controller need to synchronize. The view needs to tell the controller that something did happen, or something will happen, or ask if something should be allowed to happen. To do this, the controller sets itself as the view’s delegate through protocols.

Important: views do not own the data they display!! The view should be as generic as possible.

## Logarithmic Identities

### 06.17.2013

Recall, logb(y) = x ⇔ bx = y.

Then,
logb(xy) = logb(x) + logb(y)
logb(x/y) = logb(x) - logb(y)
logb(xp) = (p)logb(x)
logb(x) = logk(x)/logk(b)

## a11y

### 08.26.2012

I gave a tech talk on web and mobile accessibility during my internship this summer. Hopefully the slides will help people who want to learn more about a11y, or are also giving a presentation.

I did demos using VoiceOver showing the differences between good and bad websites (see examples in the slide notes). I didn’t have enough time, but the same can be done with mobile apps using VoiceOver or TalkBack on iPhone and Android. Hopefully the Windows phone will get a screen reader in the near future.

Some tools for testing accessibility:

Accessible design is universal design. Designing for accessibility shouldn’t be limiting. It should help you focus on what’s really important – what’s the main goal of your product, and how can users achieve this goal?

We’ve made some great changes in the physical world to promote accessibility. The virtual world should be just as accessible.

## Android Application Overview

### 08.22.2012

A good overview of Android is in this lecture by Yoni Rabkin, which explains the different parts of an app.

• An Intent is a description of an operation. It conveys requests between all different components of the system; an important thing intents do is launch Activities.
• An Activity is a single, focused thing that a user can do. It presents a visual user interface for a single task.
• One activity calls another activity (stack).
• A Fragment is a piece of the interface or behavior that can be placed in an Activity.

A View is a basic component of the user interface, responsible for drawing and event handling. It defines the visual content of an Activity. A Service runs in the background for an indefinite period of time. It’s like an Activity without a UI. A BroadcastReceiver broadcasts and reacts to intents sent by sentBroadcast(). A ContentProvider makes data available to other applications.

Layouts are determined by .xml files in the res directory.

Android documentation is super helpful, especially the Application Fundamentals. Eclipse is actually pretty easy to set up, and worth it when you’re doing a lot of Java programming (alt+shift+R to the rescue!).

## Mac Software

### 08.21.2012

I finally bought a new laptop! A 13-inch Macbook Air*.

I previously had a HP tx2000 tablet PC**. It lasted me nearly four years, with a motherboard replacement after 2.5 years. :/ (The model has major heat issues.)

I had made a list of software I had installed; I figure I should update it for Mac.

I mapped the Caps Lock to the control key and now I am happy. :) Here’s everything I have installed now:

* 256GB SSD, 8GB RAM, 2.0GHz Intel Core i7 running Mountain Lion
** 300GB HDD, 4GB RAM, AMD Turion X2 Dual-Core Mobile RM-72 2.10GHz running Windows Vista Home Premium

## Argument Passing

### 08.13.2012

First, what’s pass by value and what’s pass by reference? This Stack Overflow answer sums it up quite nicely:

• Pass by reference is like sharing an URL. If you and I both have the URL, we’re viewing the same web page. If changes are made to the page, we both see it. If you delete your URL, the page is still there.
• Pass by value is like having a printout of the page. If changes are made to the original web page, you can’t see it. If you make changes to the printout, the original doesn’t change. If you destroy your printout, the page is still there.

I came by this question because I’m doing some Android programming. I wanted to store a reference (which, in Java, is really just a pointer to an object) to a button to access later; however, I would be left with a dangling pointer if the Activity containing the button is destroyed! Anyways, this somehow devolved into finding out more about Java, and that it’s pass by value.

A swap function is the simplest test for whether a language is pass by value or pass by reference.

So for Java…

public class PassByValue {
static void swap(int a, int b) {
int temp = a;
a = b;
b = temp;
}
public static void main(String[] args) {
int var1 = 1, var2 = 2;
System.out.println("Before swap:");
System.out.println("var1 = " + var1);
System.out.println("var2 = " + var2);
swap(var1, var2);
System.out.println("After swap:");
System.out.println("var1 = " + var1);
System.out.println("var2 = " + var2);
}
}

Which gives:

Before swap:
var1 = 1
var2 = 2
After swap:
var1 = 1
var2 = 2

That’s what we expected, since Java is pass by value.

To have a valid swap method in Java, the variables you want swapped must be in a class. Then your method would take in the class references as its arguments. This still isn’t pass by reference, though - it’s passing the references by value.

def swap(a, b):
temp = a
a = b
b = temp
var1 = 1
var2 = 2
print "Before swap:"
print "var1 =", var1
print "var2 =", var2
swap(var1, var2)
print "After swap:"
print "var1 =", var1
print "var2 =", var2
Before swap:
var1 = 1
var2 = 2
After swap:
var1 = 1
var2 = 2

Python is also pass by value! But hmm…

def swap(a, b):
temp = a[0]
a[0] = b[0]
b[0] = temp
var1 = [1] var2 = [2] print "Before swap:"
print "var1 =", var1
print "var2 =", var2
swap(var1, var2)
print "After swap:"
print "var1 =", var1
print "var2 =", var2
Before swap:
var1 = [1]
var2 = [2]
After swap:
var1 = [2]
var2 = [1]

Yeah, Python is still pass by value. It’s like Java, though, in that it has object references. Everything in Python is an object; however, objects can be mutable or immutable. Lists are mutable, so they can changed in place.

Fortran is pass by reference, C is pass by value (though you can imitate pass by reference through pointers), C++ is both, etc. Fun stuff!

## PC Software

### 07.11.2012

I’m thinking of getting a new laptop, so I compiled a list of all software on my current computer (Windows Vista).

## How are calorie counts determined?

### 06.19.2012

The Calorie unit on most food packages is actually a kilocalorie. A calorie is a unit used to measure energy - specifically, the amount of energy needed to raise one kilogram of water by one degree Celsius.

The original method to measure the number of kcals in food directly measured the energy it produced by placing it in a bomb calorimeter (a sealed container surrounded by water), burning it completely, and measuring the rise in water temperature.

Nowadays, most calorie values are estimated using the Atwater system, which calculates the calories provided by energy-containing nutrients in the food: protein, carbohydrates, fats, and alcohol. Since fiber is not digested and utilized by the body, the fiber component of foods is usually subtracted from the total amount of carbohydrates.

The Atwater system uses 4 kcal/g for protein, 4 kcal/g for carbohydrates, 9 kcal/g for fats, and 7 kcal/g for alcohol. These numbers were originally obtained by the bomb calorimeter method.

## Source Code Optimization

### 06.19.2012

This is a really interesting talk, given by Felix von Leitner at the 2009 Linux-Kongress. It has great examples and tests, using various versions of gcc, icc, llvm, suncc, and msvc.

The main points are 1) optimization is important, 2) readable code is often more important, and 3) know how your compiler optimizes code, and let it optimize.

Some definitions:

• out-of-order superscalar executionout-of-order execution is where the processor executes instructions based on the availability of data rather than the original order in the program; a superscalar processor executes more than one instruction per clock cycle by simultaneously dispatching instructions to multiple execution units (instruction level parallelism).
• register renamingchanging the name of some registers to decrease the need for serialization of program operations imposed by the reuse of registers by those operations.
• cache associativityassociativity deals with the number of places a particular entry can be mapped to. A direct mapped cache means an entry has only one place in the cache it maps to, a two-way set associative cache means an entry has two places it can map to, etc. Caches with more associativity have a lower cache miss rate, but it takes longer to check whether an entry is in the cache or not.
• strength reduction - a compiler optimization where expensive operations are replaced with equivalent and less expensive operations (e.g. bit shift for multiplcation)
• tail recursion - when a subroutine call happens inside another procedure as its final action (i.e. the call site is at the tail position)

Some C stuff:

• #define - uses the C preprocessor; the compiler doesn’t see it, so it’s not visible in the debugger. Basically a “find and replace.”
• const - declares something as unmodifiable; it cannot be assigned to after it’s initialized. Visible in the debugger, but it takes up memory (unless static is used).
• static - allows a variable inside a function to keep its value between calls, and allows global variables to be “seen” in only the compilation unit it’s declared in. (Using it to keep state between function calls is not thread-safe!)
• enum - a way to map identifiers to integer values. Visible in the debugger and uses no memory.
• volatile - tells the compiler not to optimize anything that has to do with a variable. Usually, a compiler caches variables in registers for optimization purposes.

Now for optimization!

1. Inlining
• the compiler will usually inline
• destroys code locality
• make helper functions static
• difference between gcc and C99
2. Range Checks
• compilers optimize away superfluous checks
• CSE (common subexpression elimination) eliminates duplication
• invariant hoisting moves loop-invariant checks out of the loop
• the compiler and linker can sometimes remove
• …unreachable code
• …a static function that is never used
• …whole .o/.obj files that are not referenced
4. Pre- vs. Post-Increment
• use ++a instead of a++, since
• this rarely matters today (useful in the 90’s)
5. Fancy-Schmancy Algorithms
• use a list for 10-100 elements
• fancy data structures help on paper, but rarely in reality
• more space overhead for the structure means less L2 cache left for data
• if you manage a million elements, use a proper data structure
• if you can’t explain it on a beer coaster, it’s too complex
6. Memory Hierarchy
• important optimization goal these days!
• use multiplication instead of shifting costs five cycles
• conditional branch misprediction costs ten cycles
• cache miss to main memory costs 250 cycles
7. Pre- vs. Post-Increment
• use ++a instead of a++, since
• this rarely matters today (useful in the 90’s)

In short - if you do an optimization, test it on real world data. If it’s not drastically faster and makes the code less readable, don’t use it.

## What does unrolling a loop do?

### 06.18.2012

Loop unrolling is a form of loop optimization. It increases a program’s execution speed by reducing loop overhead (instructions that perform loop control and access), and control hazards and stalls (the need to wait until a branch is computed and resolved). This is usually done by an optimizing compiler, but you can manually unroll loops as well.

An interesting and notable implementation of loop unrolling is Duff’s device, discovered by Tom Duff in 1983, which takes advantage of fall-through in a switch statement. It lowers the number of branches a serial copy has to make by assigning up to eight values in one iteration.

Manual unrolling loops is uncommon these days. There’s a space-time tradeoff, and the compiler usually unrolls loops for optimization anyways. However, it does make sense when you can break dependency chains. An out-of-order CPU can perform other calculations, even when one of the branches has stalled.

## Thomas Wouter’s Python Talk

### 06.15.2012

Watched Thomas Wouter’s Google talk on Python today. The pace was pretty fast for me, but it’s a good video. I went back and reviewed a couple things to make sure I understood it.

Here’s the first snippet of code he gave:

def func(arg1, arg2=Foo()):
print "Entering func"
def inner_func(arg3=arg2):
print "Entering inner_func"
return arg1, arg3
arg1 = arg2 = None
return inner_func

def Foo():
return "Foo()"
def func(arg1, arg2=Foo()):
print "Entering func"
print "arg1 =", arg1, "; arg2 =", arg2
def inner_func(arg3=arg2):
print "\nEntering inner_func"
print "arg1 =", arg1, "; arg3 =", arg3
return arg1, arg3
print "arg1 is still", arg1, "and arg2 is still", arg2
arg1 = arg2 = None
print "arg1 =", arg1, "; arg2 =", arg2
return inner_func

print 'Calling f = func("hello")'
f = func("hello")

a, b = f()
print "f() returns", a, "and", b

arg1 = "good"
c, d = f(arg3="bye")
print 'f(arg3="bye") returns", c, "and", d

Which outputs:

Calling f = func("hello")
Entering func
arg1 = hello ; arg2 = Foo()
arg1 is still hello and arg2 is still Foo()
arg1 = None ; arg2 = None

Entering inner_func
arg1 = None ; arg3 = Foo()
f() returns None and Foo()

Entering inner_func
arg1 = None ; arg3 = bye
f(arg3="whoa") returns None and bye

This shows some important aspects of Python, notably that everything is runtime, executed top-to-bottom. def and class define functions at runtime. Function code is compiled into a “code object”, then wrapped in a function object when def is executed.

In my example, Foo() is another function, so when def func(arg1, arg2=Foo()) is executed, Foo() is evaluated and gets assigned to arg2.

When func is called, inner_func is created. The default for the arg3 argument is assigned arg2, which is currently "Foo()".

arg1 and arg2 are then reassigned. This shows nested scopes pretty nicely - although both of them were changed, only arg1 will be None.

Execution happens in namespaces (which are dicts) - modules, functions, and classes all have their own namespaces.

I urge you to do whatever you do for no reason other than you love it and believe in its importance. Don’t bother with work you don’t believe in any more than a spouse you’re not crazy about.

Resist the easy comforts of complacency, the specious glitter of materialism, the narcotic paralysis of self-satisfaction.

And read. Read all the time. Read as a matter of principle, as a matter of self-respect. Read as a nourishing staple of life.

Develop and protect a moral sensibility, and demonstrate the character to apply it. Dream big, work hard. Think for yourself. Love everything you love, everyone you love with all your might.

The fulfilling life, the distinctive life, the relevant life - is an achievement. Not something that will fall into your lap because you’re a nice person.

You’ll note the founding fathers took pains to secure your inalienable right to life, liberty, and the pursuit of happiness. Quite an active verb, “pursuit.” Which leaves, I should think, very little time for lying around watching parrots rollerskate on YouTube.

Get busy. Have at it. Don’t wait for inspiration or passion to find you. Get up, get out, explore, find it yourself, grab hold with both hands.

Now, before you dash off and get your YOLO tattoo, let me point out the illogic of that trendy little expression, because you can and should live not merely once, but every day of your life. Rather than “you only live once,” it should be “you live only once”; but because YLOO doesn’t have the same ring, we shrug and decide it doesn’t matter.

None of this day-seizing, though, this YLOO-ing should be interpreted as license for self-indulgence. Like accolades ought to be, the fulfilled life is a consequence, a gratifying by-product. It’s what happens when you’re thinking about more important things.

Climb the mountain not to plant your flag, but to embrace the challenge, enjoy the air, and behold the view. Climb it so you can see the world, not so the world can see you.

Go to Paris to be in Paris, not to cross it off your list and congratulate yourself for being worldly. Exercise free will and creative independent thought not for the satisfactions they will bring you, but for the good they will do others - the rest of the 6.8 billion, and those who will follow them.

And then, you too will discover that the great, curious truth of the human experience is that selflessness is the best thing you can do for yourself.

The sweetest joys of life, then, come only with the recognition that you’re not special. Because everyone is.

## Killing of Infected Cells By Cytotoxic Lymphocytes

### 02.07.2012

Method A. Perforin and granzymes

1. TCTL binds to the target cell due to class I MHC interaction as well as other adhesion proteins.
2. TCTL release perforin by fusion of membrane vesicles with the cell membrane of the infected cell.
3. Perforin generates a pore in the target cell, allowing entry of granzymes (a class of proteases).
4. Proteolytic action of granzymes induce apoptosis in the target cell.

Method B. Fas L and Fas

1. Fas L on the surface of TCTL binds to the Fas ligand on the infected cell.
2. Trimerizaion of Fas on the target cell results in activation of the proteolytic signaling pathway.
3. Target cells dies from apoptosis.

These methods differ in terms of the recognition process. NK cells kill in these manners as well.