Refactoring returns by introducing booleans

Consider code that looks like:

1. void foo() {
2. if( some-condition ) return;
3. if( some-other-condition ) { do-something; return; }

etc.

Say this code is replicated in several places. Obviously we want to extract it into a common subroutine or class - the extract method refactoring.

If you can jump right to the end of the refactoring, great. But, I admit that I have occasionally tripped myself up doing this. (The example is, of course, oversimplified.)

So, here's a micro-refactoring that can help:

Extract to a function that returns a bool, named check_and_do_some_things_and_maybe_return()

1. void foo() {
2. if( check_and_do_somethings_and_maybe_return() ) return;
3. ...
   

1. bool check_and_do_somethings_and_maybe_return() {
   
2. if( some-condition ) return 1;
3. if( some-other-condition ) { do-something; return 1; }
4. return 0;
5. }
   

etc.

This requires editing each return.

If you want to avoid that, maybe add a boolean temporary to the original code - instead of returning immediately, delay all of the returns to

1. void foo() {
2. bool return_early = false;
   
3. if( some-condition ) return_early=true;
4. if( !return_early ) {
   
5. if( some-other-condition ) { do-something; return_early = true; }
6. if( !return_early ) ...
7. }
8. if( return_early ) return;

THEN you can safely extract the method a line or statement at a time.

Company abandons internal news servers; thoughts about PC versus Google

Minorly off-topic, but I feel impelled to note that _I_n_t_e_l_ has just ZBB'ed its internal NNTP news servers. Actually, they were ZBB'ed many years ago, but volunteers kept them going. Those volunteers may now be ZBB'ed. New volunteers may arise; heck, I may; but the path of least resistance is to give up on getting USEnet news inside the company, and go to some external service. E.g. today I am posting from Google Groups.

Personal relevance to comp.arch: my employer's internal news servers have been my main connection to comp.arch since 1991. Brief exceptions while I was in Madison and at AMD. Prior to joining _I_n_t_e_l_ I participated in comp.arch and its predecessor net.arch on news servers from the University of Illinois and from Gould and Motorola. I still maintain that I learned more computer architecture from comp.arch than I did in any school; moreover, I am fairly confident that I would never have gotten my job with _I_n_t_e_l_ without my comp.arch mediated acquaintance with Bob Colwell.

Generic relevance to comp.arch: this is a trend. Actually two trends.

Trend #1 is that less and less personal computing can be done at work, and that more and more work related computing is "freeloading" on personally paid for computing.

Most people used to have only one email address that they used for both work and personal matters. You can still do this, but it is becoming increasingly hard to do so because companies like my employer do not allow you to access the corporate network from your own computers; you can only do so from a company owned device.
So you have a personal mail service, as well as your work mail service. Maybe your personal mail servce is from an ISP, and changes whenever your ISP changes, you move, or when Qwest gets bought out by Verizon. Maybe you have your own domain.
But your company doesn't allow you to run POP across the firewall. Similarly for newsgroup access: your company desn't allow you to run NNTP across the firewall.

This leads to Trend #2: Google. More generically, the rebirth of "Big Iron", centralized, computer service companies.
Google *is* "Big Iron". Maybe not in the IBM mainframe sense, but anyone who has seen a Google machine room knows that it is a completely different scale than a desktop or laptop PC.
For many years I tried to keep my personal computing environment PC based. I ran my mail reader on my laptop or desktop PC, sometimes via a client technology such as POP, IMAP, sometimes peer-to-peer stuff like SMTP. Similarly, up until now I have read news on my laptop or desktop PC. When I saved a file, it was saved on my PC's hard disk. I could not access my environment of saved files and email without being on my PC. Maybe I could read my email from other computers, but I did not have my mailreading environment on those other computers, so I tried to avoid doing so.
But, not being able to access my personal email from work - no POP, no ssh - was the last straw. I switched to Google mail. Now I can access my personal email from any computer - at work, at home, from my wife's computer. From my relatives' computers. I no longer need to drag my personal laptop around with me.

Downside: I cannot access my Google email when I am not connected to the net. For many years this was the biggest reason that I stayed PC based. Broadband took a long time to get to many of the places where I spend time, like Oceanside, Oregon, and the Ottawa river valley in Canada. Broadband is still not available in many of my favorite places, such as Eastern Oregon. Heck, cell phone service is not available. (I am waiting for reports of the Microsoft/KVH mobile broadband with interest.)
Perhaps most important for business folk, I cannot access Google email on a plane, when I am not connected to the Internet.
Yes, I know: you can access Google mail via POP, downloading it to a mobile PC where you can read it disconnected. But that just puts you back in the "your mailreadimg environment lives on only one PC" mode. So far as I know, there is no way to download Google mail to your PC, and then upload back to Google any annotations, tags, classifications, and spam markings you have made to your email while disconnected.
I hope that Google will soon remedy this, and provide disconnected operation, not just for email, but also for other Google services such as Google groups.

Interestingly, moving to Google mail has provided more freedom from the point of view of form factor. In my "my mailreading environment lives on a single laptop PC" days, I needed to have a laptop that met my minimum needs for all common situations. E.g. it had to have a big enough screen, enough disk, and a keyboard. But now that I am Google based I can seriously consider reading email on a keyboardless tablet in my living room, or a PDA, or... Since I can always go to another device. I.e. I am more likely to buy a "widget" specialized computer now that I am using Google mail than I was when I used a PC.
I hypothesize that this is true not just of me, but also of other users. Perhaps the long awaited flowering of specialized devices for ubiquitous computing is now about to begin.

Terminology change: I used to read my mail on my laptop PC. Now I read it on Google, via a web browser that happens to run on a PC, but which could run elsewhere. I used to be a PC user. Now I am a Google user.

USEnet news is just another information service, like email. Same considerations apply. Since I have switched to Google mail, I might as well switch to Google groups. Ditto RSS, and other information services.
What I really want is to receive all of my information inputs in a common environment, that can seamlessly prioritize and sort email, USEnt news, RSS, regular news, IM, and telephony. Google is the most likely company to achieve this.

Interestingly, I have been forced into schizophrenia. My work information feeds are in one place, my personal feeds in another. At the moment it appears that the personal feeds on Google are more integrated, have better search abilities, etc., although far less storage.
Will this keep up? Or will the quality of information management at work play leapfrog with Google? I do not know... but I predict that at least some fraction of companies will just outsource their employees email, etc., to Google. I.e. I predict that Google will be able to provide a single stop for both work and personal information management. And that because of this, it will have a larger critical mass than companies that are stuck just supporting an individual's work computing and information needs.

Returning to trend #1: not only will less and less personal computing be done at work, but more and more work computing will be done personally... because the personal computing environment, whether Google based or whaever, is pulling ahead of the work environment. (Unless Google takes over the work environment, as predicted above.)
The item that sparked this post is just an example: reading USEnet newsgroups such as comp.arch is recreation, but I also fairly regularly post queries to newsgroups such as comp.lang.c, etc., for work related questions. Closing down the company's internal news service, of course, means that I will be now doing this using my personal computing resources. I.e. Google groups.
More evidence of this trend: back in the old days companies paid for 2nd phone lines for computer access. Nowadays you are expected to pay for your own broadband access, and to use it for after hours work. I keep meaning to take an income deduction for my broadband for tax purposes, since the logs plainly show that it is mostly used for work, not pleasure.

Summing up:
Prompted by: my company abandoning internal new servers.
Hypothesis: there is a trend away from PC based computing and information services, towards centralized computer services like Google.

The computer industry battle is not _I_n_t_e_l_ versus AMD, or Microsoft versus Linux. It is the PC versus Google.

(Here, I use "Google" as representative of web based computing services, ubiquitously accessible so long as you have Internet access.)

Lifestyle computers

Labor Day weekend, sitting on the beach - I'm not surfing because I am watching my daughter play in the sand. No book to read. It would be nice to be able to use my computer on the beach - but it would have to be a laptop with no airholes for cooling, no PC-Card slots. Sealed, no entry for sand or water. Plus a daylight visible screen.

Merging my diverged CVS trees

I hope that I can use Git's content based features to merge my diverged CVS trees.

Git, Renaming, etc

Git does not track file renames.

Linus's email, http://permalink.gmane.org/gmane.comp.version-control.git/217, is essentially correct, but shortsighted. Linus argues that file renames are just a special case of moving content around. E.g. how does file rename tracking help you if you take a source file foo.h, move all of its content to bar.h, and then put #include "bar.h" inside foo.h? Linus argues that a content based tool that can detect this sort of movement, is more useful than tracking renames in Git.

Linus is right. But, Linus is shortsighted. Linus is considering only one usage model: that of a programmer studying code history. There is a human in the loop.

I want to use a version control system such as Git to perform such actions when a human is not in the loop.

E.g. I want to use Git, instead of RCS, as the version control system in twiki. Then, if a user requests http://mytwikisite.net/OldTopic, I can tell him or her that OldTopic has moved to NewTopic. To do this, the content tracking system must be able to make a single suggestion.

Of course, a content tracking system can make a single suggestion. But, it may get confused - e.g. two different wiki pages may start off from a common answer. Some human may have to decide who is the most logical primary choice. If that choice has been made, why not record it? Which amounts to recording the "primary" renaming.

Similarly, even a wiki may want to have a content tracking system that has a human in the loop. But it is nice to have a fully automated system with no human in the loop, that takes advantage of recorded rename tracking.

And, I hazard, even an SCM will need the fully automated version.

I.e.:

Rename tracking is a convenience.

Content tracking, with or without a human in the loop, is of additional value.

Content based filesystems and VC

It's time that I switched to Git for version control of my home directory - which has CVS'ed for the last, what, 10 years, maybe longer - and which has also been RCS'ed, SCCS'ed, and, briefly, BK'ed.

A few months ago Linus told me that Git was ready for folks like me to use it. At the same time he also discussed the following issue:

Git is, essentially, a content based filesystem or object store. It uses the SHA-1 cryptographic hash of a file as that file's name.

When last Linus and I talked (which was also the first and only time we have ever talked in person, at a restaurant - we've only briefly talked via email and newsgroups otherwise) Linus assured me that Git could handle the case where two objects had the same hash. I haven't seen how it is handled in the code. The Git discussion groups seem to be populated by people who cannot imagine that a collision would ever occur. I'm willing to believe that Linus has handled it properly. I'm going to use this blog to discuss what properly is.

First off, the basics: I'm with Val Henson, http://infohost.nmt.edu/~val/review/hash.pdf: using compare-by-hash without being prepared to handle collisions is bad, Bad, BAD. Given a large enough collection of files, a hash collision will occur. Worse if one can be constructed by a malicious user seeking to corrupt a repository.

But I really like the convenience and efficiency of compare-by-hash --- I call it "content based" addressing. So I want a content based scheme that handles collisions.

I can't understand why everyone doesn't do it: it's pretty simple.

E.g. in the object store, you create an index that maps hashes to object names. The object names could still be the cryptographic hash, perhaps with an instance number appended: i.e. the first object in the repository that has hash F00 would be named F00-0, the next F00-1, etc.
If you are so confident that there will never be collisions, you will only see F00-0 names, right? What does it harm you to append the instance number?

Or, you could use some other scheme for creating a unique name for the repository, such as a sequece number. In fact, I would probably suggest using both such designation schemes: sequence numbers inside the repository are more likely to need to be changed when two different repositories are merged. Hashes are more likely to be unique - although, if you merge two repositories that both have F00-0 objects, which are different, one is going to be named F00-1 after the merge. But, again, for those who are confident that collisions will never occur, you will never see this _slight_ renaming.

The only way in which this deviates from compare-by-hash content based systems such as Monotone is that, when you are adding an object to the repository, you don't just stop when you have computed the hash, and have seen that the hash is already in the repository. You have to compare the new object to the object that is already in the database that has the same hash. I.e. you use the hash to determine who to compare to, but you still do a full comparison.

Note: to compute the hash of the new object, you have to scan all of its bytes. That's O(n) work. To do the full comparison is still O(n) work - albeit with a bigger constant multiplier, circa 3X (one scan for the hash, then a scan of both the new and old object for the compare).

This suggests that you may not want to use a cryptographic hash of the entire file's n bytes. You may want a sampled hash. E.g. a hash of the first kilobyte, or a random selection of bytes. The purpose of the hash is now just to reduce the probability of collision, not eliminate it.
(Of course, the real issue is that no hash ever eliminates the possibility of collision:
people just fool themselves that it does.)

Another trivial optimization is to use the object size as well as its hash. If two objects that have the same hash differ in size, you can avoid the full comparison. If you are one of those people who believe that SHA-1 hash collisions can never occur, then certainly they will never occur for objects of the same size. So, by your own standard of belief, the full file comparison will never be done.

So, let's compare what I propose - using the hash as a hint, but handling collisions - to what Monotone did, using hash as a name, not providing for collisions. Let's call them collision-handling-content-based, and collision-neglecting-content-based:

If you believe that hash collisions will never occur:

• when naming objects in the repository, my collision-handling and Monotine's collision ignoing approach will work the same.
  
• when adding objects to the repository, my approach *might* require a full comparison - but the simple expediet of including the object size in the hash comparison avoids this -- in all of the cases where no hash collision occurs.
  

I.e. my collision handling approach and Monotone's collision ignoring approach are equivalent, so long as no collisions occur. And, of course, if collisions occur, Monotone breaks, but my approach still works.

The only reason that I can possibly imagine for not using my approach is code complexity. Why add code that will never be exercised? How do you test it? When I started writing rcs-file-merge -- until I learned that Linus was writing Git - I planned to use the content-based approach. But, I deliberately used a really weak hash - UNIX checksum - to deliberately create collisions, so that I could test that I could handle them. Found collisions in my home directory. Of course, a stronger hash would be used in actual production.

I really, really, hope that Git handles hash collisions. As I describe above, it is very straightforward, and costs nothing in performance.

Outlook woes / ISO a single reading interface

Last week I switched back to Outllook email. It only took 4 days until Outlook corrupted an OST file, and hung sending mail. My hands and shoulders and wrists hurt, because of Outlook's lousy human interface design.

Also, I was reading USEnet news and email together in EMACS Gnus. Now, with Outlook, my USEnet newsgroup reading rate has fallen off. I am too lazy to use multiple interfaces.

Only saving grace is that I have moved personal stuff to Google Mail and Calendar.

Unfortunately, now I have more different interfaces - Google Mail, Outlook, USEnet.