Oleg Andreev

Knight’s Principles

Knight’s Principles

— Never do any work that you can get someone else to do for you

— Avoid responsibility

— Postpone decisions

— Managers don’t do any real work

— Premature optimization leaves everyone unsatisfied

— Try not to care

— Just do it!

— It’s not a good example if it doesn’t work

— Steal everything you can from your parents

— Cover your ass

“Each object will do a seemingly insignificant amount of work, but somehow they add up to something much larger. You can end up tracing through the system, looking for the place where a certain calculation happens, only to realize that the calculation has been done and you just didn’t notice it happening.”

Is iPad an autonomous device?

When you buy one, the first thing you see is “Connect to iTunes” screen. You need some “big” computer to start using it. If I’d like to buy one to my grandma, who does not have and cannot use a modern desktop computer, I have no problem with initial setup using my macbook.

The only way to back up your data is, again, to connect to iTunes. Most of the apps keep the data on the server (btw, I hate when people say “in the cloud”), but you still have photos, notes and documents on the device. I don’t know whether MobileMe and iWork.com actually back up the data or just share selected files, but they could be easily extended to do just that later when more people will try to use iPad as a primary device, not just as a “node in a digital hub”. Right now, mobileme offers e-mail hosting which can also synchronize notes. But current version of iPhone OS does not offer notes sync using e-mail account (while Mail.app on Mac OS X does).

If my grandma has a problem with her iPad she might lose her pictures and notes. However, my grandma particularly is not going to take much photographs and notes, so that is not much of a problem.

As of now, the only obstacle to making the iPad an only computer in the house is to get rid of big-brother iTunes requirements by replacing it with a internet service to do the very same thing. I bet Apple is moving towards making iTunes a 100% capable web application in addition to desktop version.

Programming songs

Monzy — Kill dash nine

Coder Girl

IE is being mean to me

Write in C

Zed Show — Matz Can’t Patch (show text)

Pitfalls of lack of encapsulation

Tony Albrecht, Technical Consultant at Sony, tells a story about memory performance and object-oriented programming style.

If you read the story carefully, you will notice that the performance problem was actually solved by writing class-specific allocators (that keep each object of the same kind in a continuous array) + doing recursive algorithm in two passes.

Tony knows very well what happens on hardware level, but he is not good at object-oriented programming. Let’s see what is wrong with his code.

In the beginning, their code is not well organized: instead of multiple distinct objects with small independent data structures they had fat nodes with matrices, vectors and other structures built-in. Because of that, the various kinds of data were interleaved and didn’t play well with the cache.

First optimization: they made the code object-oriented by factoring big data structures like Matrix and Vector out of the Node. Then, they used the incapsulation (fundamental principle of OOP) to provide custom allocators with continuous memory zones. This is only possible in a proper object-oriented code when objects of one kind do not interfere with objects of another kind other than with explicit messages. So you can optimize memory layout for Matrices, provided their behavior is not changed, and you will not break some other part of the code. OOP helped to gain 35% of performance.

Second optimization: they splitted the recursive update procedure into two phases to avoid going bottom-top adding WBS (world bounding sphere) more than once per parent node. This would save about 25% of CPU time (assuming binary tree and no overhead on leaves). But they actually got about 50-60% increase because they used continuous allocator for nodes like they did with matrices and vectors.

This is all understandable. But there are two design decisions which are not justified:

1. In the first optimization Tony claimed that “excessive encapsulation is BAD” (slide 20) and thus decided to put raw pointers to the array of matrices and vectors outside of their respective nodes into the loop which iterates over the nodes (slide 89):

for (int k=0; k < innerSize; k++, wmat++, mat++, bs++, wbs++)
{
*wmat = (*parentTransform)*(*mat);
*wbs = bs->Transform(wmat);
}

Do you see those wmat, mat, bs, wbs pointers? These are private things pulled out of node objects under the claim of “excessive encapsulation is BAD”. Now object does not control its data and once you’d like to add another special-effects matrix over the node, you’ll have to learn not only the Node class, but the entire rendering codebase!

This is how it should be done actually:

for (int k=0; k < innerSize; k++)
{
children[k]->updateWithParentTransform(*parentTransform);
}

Where updateWithParentTransform does the job involving wmat, mat, wbs and bs and gives you guarantee that this is the single file where these variables are accessed directly.

Also note that this method will be perfectly inlined by C++ compiler or smart dynamic Smalltalk/Self/JVM system, so the result code will do the same operations and memory accesses as the manually inlined code with “naked” private pointers.

2. The second claim is to “Make the processing global rather than local” (slide 73). This is also awfully wrong. Tony suggests splitting the tree of nodes into arrays of nodes sorted by level. It is not only inflexible (or requires quite complicated algorithms to maintain the invariant), but is also pointless.

We already have these class-specific continuous allocators which put nodes close to each other. We already have extracted huge data structures from the nodes, so that we may keep a lot of nodes in just a fraction of the L2 cache while the rest of it is used for matrix operations. And we already split up the algorithm so that the parent’s boundary is not updated too often. But still, he claims some performance gain out of the fact that nodes are not traversed recursively, but rather linearly using quite a brittle memory layout.

There is no point in that since node objects are so small that most of the data you need to update children using parent’s transformation matrix is already in the cache. And for the cached data there’s no difference how it is positioned: the access time is constant.

But he did not only traded nothing for more complicated code, but also made his life harder to move from a single CPU to multiple CPUs (say, GPU): only recursive algorithms and encapsulation may give you an option to parallelize computation. By flattening algorithms and breaking encapsulation Tony cut himself a way to scale the performance horizontally (or, equally, made it harder to automatic parallelizing compiler to do its job).

It is very important to know how things work on low level, but is also important to know how to incapsulate low level complexity and free your mind for greater deals.

Update: Tony replied showing that I’m not entirely right. (March 18, 2010)

Android vs. iPhone: the good, the bad and the ugly

In last two months I had an opportunity to build two versions of the same application: on iPhone and Android. Both applications are basically navigation/tableview-based browsers for existing French website. Absolutely nothing extraordinary about the whole thing, but it is interesting how similar features could be accomplished on competing platforms.

The Good

First of all, you don’t have to register or pay a fee in order to start developing and testing on a device. Also, you may work on Windows and Linux, but I have not tried that out.

There’s a very flexible layout framework which allows you to position elements relative to each other, to the parent and to the content. You may wrap layout around its content, but also tell it to fill N% of free space. Or fill the whole parent width (or height). Android layout are much more flexible and still simple comparing to Cocoa and even HTML+CSS. Even though the Eclipse IB-like plugin sucks, XML layout language is easy to learn and is not hard to type.

Layouts seem to be simpler and more light-weight than iPhone views: in iPhone I have to render tableview cell by hand (all these tedious pixel calculations: paddings, margins and conditional layout depending on missing text) to maintain smooth scrolling; on Android an straight-forward XML layout for a cell was enough. This is a real time-saver.

Resolution-independent metrics are very powerful: you have regular points and pixels (device-dependent), device-independent points (dips) and device- and textscale-independent points (sips). Elements with dip-dimensions will be sized equally on different screens and elements with sip-dimensions will scale according to user preferences.

The Bad

The first bad thing about Android is Java. Though it is not a language or VM. It is the way people write Java code. They do it fundamentally complicated in every single place. My application does not have any sophisticated features. It is damn simple. And iPhone has simple tools for that. Android and Java have tools to build a space shuttle.

Every single thing in Java (and I’m speaking about both legacy java.lang.* and modern android.* APIs) makes you use a couple of classes and a couple of interfaces. The classes themselves usually inherit 4 levels of superclasses and countless interfaces. In sake of code reuse, the core functionality which you use on a single object is usually split across several classes which makes you switch between various doc pages enormous amount of times. This creates a great pressure on developer’s brains: in process of building a 5-minute feature you have to load your head with almost useless hierarchical structures.

Java developers would say that on the other hand you have a rich reusable toolkit. In fact, the simple thing like network connectivity (parse url, asynchronous download over http, setting and reading http headers) could not be done using a single doc. In iPhone I’ve build a little handy OAHTTPQueue around just a couple of Cocoa classes: NSURL, NSURLRequest and NSURLConnection. I was learning Objective-C and Cocoa from scratch and it took just a couple of hours to implement a descent queue. When I switched to Android I already knew what I’m going to build and how should it work. But it took almost three days to get through 3 (!) huge independent packages android.net.*, org.apache.http.* and java.net.*. Each package had some useful bits on its own, but none was easy to take and build something right away. None contained a simple asynchronous API. Finally, I got to take single thread executor from java.util.concurrent and use a blocking HTTP API from org.apache.http. Other options were as high-level as writing to a socket by hand. The devil of Java is very well illustrated by apache HTTP library: not only it has tons of classes and interfaces, these classes are scattered across 10 sub-packages. In Cocoa you can do all the same things with about 20 NSURL* classes, using 3-4 (!) of them 90% of the time.

In average, for each Cocoa class there are 10 classes and interfaces in Android providing about the same functionality. In other words, Cocoa is 10 times more productive than Java.

Android lacks good programming guidelines. With that amount of options Java spits on you, the guidelines are absolutely a must.

It seems, Google does not care much about the phone. I got lots of stupid errors in MapView. It also lacks built-in pins, annotation pop-ups and callbacks for region-changing events! I had to implement pins and pop-ups by myself. And without useful callbacks, there’s a repeating timer which polls MapView properties and triggers a callback after user stopped dragging/zooming the view.

The Ugly

UI is slow and does not feel right. Scrolling momentum is not natural, every screen opens with a noticeable delay, maps are slow and some screens are 16bit. (Hello, it is 2010 already!)

Android device has physical buttons. Only 2 of them wake device from sleep: “menu” and “hang up”. Others are no-op. Very confusing.

Every application has a hidden menu. It pop-up when you click a “menu”, which is a physical button. And then you have to click a screen button. And to go back from wherever you are you have to tap a physical button again.

Android is over-engineered and under-designed platform. It has interesting model of multitasking stack of activities, but it fails completely when it comes to actual UI. There are “back” and “home” physical buttons. Pressing “back” removes current activity from the stack. Pressing “home” pushes Home Screen on top of the stack. All running activities remain in memory. And when you tap application icon from the home it opens the top-most application activity.

There are 3 lists of the applications: on the home screen, on the “placard” which slides over home screen and somewhere in the Settings (where you should go in order to remove an app). When you remove an app from the home screen it is not clear that you are not going to erase it completely (same issue with Dock on the Mac).

I gave HTC Tattoo phone to several people around me: everyone got confused by the navigation.

The End

Android UI is ugly, slow and complicated. Google is happy to put its apps and a search box in the system, but they are not interested in phone sales. Mobile carriers are interested in having an iPhone competitor, but they do not produce anything. Finally, manufacturers from China do not care about UI and global market strategy, they just produce devices.

Apple, on the other hand, is interested in both device sales and app sales. And they care about the whole chain: from hardware to end-user services.

Android seems to be dying already.

Admin pages

The average web-based shop works like this: there’s a front and a back. The front is sexy, the back is not. One group of people goes to the front to buy stuff, other group goes to the back to manage that stuff. These groups of people intersect only when those who go to the back pretend they are buyers. But still, there’s a huge distinction.

On the other hand, the real shop also has a front and a back. But those who sell stuff do not stay in warehouse all day long turning knobs to rearrange stuff on shelves. They actually go to the shop room to put things in place, see how they look and how customers explore them. In other words, a physical shop is more WYSIWYG than a web-based one.

My suggestion is to outsource to warehouse pages as little functions as possible. The shop owner should have a control on what is presented to the people. He should be able to immediately update prices, titles, rearrange things and see some basic stats which help to decide how good something sells.

Idea: Web browser for work

I’m using Safari because it is fast, simple and not ugly. But it has several annoying issues:

1. It does not return allocated memory back to system (however, it recycles it internally and does not leak). I end up with Safari eating 1+ gigs and multiple windows with multiple tabs opened. And it is not easy to restart Safari due to a second issue:

2. It does not remember opened windows and tabs automatically. If I opened 10 tabs to read later (or to work with), I have to save them in a bookmark group. And it is not easy to remove/add new pages to that bookmark group.

3. Even if I have enough memory and Safari does not crash too often, I still have multiple windows and tabs, and hidden tabs. It is hard to switch between them, especially using a keyboard.

Let’s see what we can do about it.

First, I turn to other applications I use every day: Mail, TextMate and Xcode.

In Xcode and TextMate I have a quick access to any file using a Cmd+T shortcut: I press Cmd+T, a small window pops up with a search field. I type a portion of file name and it appears in the list. Press Enter — and here it is.

Cmd+T is useful for rare switching. For more frequent switches there’s Alt+Cmd+Up to switch between .h/.m files and Alt+Cmd+Left/Right to navigate through tabs in TextMate.

In Mail I have an Inbox and the folders. Inbox contains unread/undone messages. Everything else is in the folders.

In Mail I also have a single window with a single list of items. If I want to open a particular message in another window, I double-click on an item.

With some background I may draw some requirements for a browser useful at work:

1. It should always remember all windows positions and opened websites. If it crashes, it should restore all pages as they were opened before crash. (Just like Opera did for many years, by the way.)

2. It should have a Cmd+T menu to have a quick keyboard access to all open and bookmarked pages.

3. It should remember history for a page even if it is opened in a new window or tab.

4. The unread pages should be marked so.

5. There should be a context menu item “Read Later” which puts the link into Inbox and marks it as unread.

6. It should cache all the bookmarked pages on disk (in a form of webarchive) for indefinite amount of time. Each new version should be stored as well, but not overwrite the previous one. I want to access exactly the same content I’ve once seen.

7. Closed pages should be easy to reopen. (Safari lets you reopen a window, but not a tab).

Next step is to make some UI mockups to see how silly (or not) these desires are.

Interfaces in dynamic object-oriented languages (part 2)

In the first part I suggested to use messages like to_my_interface or asMyInterface to ensure interface-compliance. This method just returns whatever object seems to be suitable for the interface, but does no actual checks. IDE like Xcode or Eclipse can do a static check for implemented methods and issue warning/error at compile time. Today I will show how to build the same feature in the dynamic system (and make it more useful).

First, two important points from the first part:

One object (sender) send a message to another (receiver) with an argument which should implement String interface (receiver will call asString method on its argument).

1. The sender does not need to perform any “casting” before sending an interface-compliant object. If appendString(obj) wants a string and you know that your object can (or should) behave like a string, you just pass it in without any conversion. Only low-level method which relies on actual string methods like substring should send asString to obtain the String interface.

2. The receiver should not perform any checks like respondsToSelector or isKindOfClass. It should only tell the argument to return something with an interface it needs.

If both sender and receiver do not check actual interface compliance, where should it happen? Obviously, inside the asString method:


# this method does not check the interface
def asString
self
end

# this method checks the interface
def asString
String.check(self)
end

How’s that different from just testing application as before? First of all, check is performed before any protocol message is send to the subject. So it is more like a “compile-time” check: some message could not be sent in runtime, but the error could be thrown before.

In addition to basic checks like missing methods String.check can also perform some unit tests (and be smart enough to test each particular class (hidden class) only once).

Needless to say that interface checks could be omitted in production mode to increase performance.