Assessments 1.0 betas 10 and 11

These improve the sorting behavior in the Benchmark Evaluator.

Assessments 1.0 beta 9

The 9th beta of Assessments is now available in the public Store repository. In this version,

• Removed the "Done" dialog after copying from the Assessment Result window via the mouse menu.
• Fixed MNU #assessment when using Evaluate All from the Benchmark Evaluator.

174 classes, 1183 methods, ~6.80 methods / class.

Assessments v1.0 beta 8

I just published Assessments 1.0 beta 8 to the public Store repository. There is a fix for a message not understood (handleSUnitFailureNotification:) in the SUnitToo bridge. Also, a menu item was renamed to better describe what it does, and a couple subclassResponsibility messages were added for the sake of completeness.

174 classes, 1180 methods, ~6.78 methods / class.

A flash back

Look at what I found in my bookshelf: a stack of 3x5 index cards I scribbled on 6 years ago regarding things I thought worth writing a book about!

I reviewed them, and as it turns out I've yet to write about the majority of the material. I think the Fundamentals book will be an opportunity to take care of the good stuff. Some ideas were bad, so I discarded those cards. And finally, a few of them actually have been treated and have been written about. Here is one that I think is particularly nice.



How about that! A card describing SUnit Based Validation dated 5/17/2002! Next to that there was a card on Complex Conditions.



I also found another one showing some of my all time favorite selectors. The messages are sent by windows to the main menu object so the [Print] action is dispatched accordingly.



Heh... "pledge to print" and "renounce pledge to print"... I still remember using the thesaurus to find the right words for that!

There is a total of 14 cards. As a result, the Fundamentals book grows further...

Regarding difficulty

A while ago I commented that it is hard to do something that has not been done before. The Smalltalks 2008 Coding Contest is one of those. I know what I want to do, I have the specs in mind and everything. But alas, there is not enough of the code written yet so it's even minimally functional. This is hard because you have to write code pretending that some other stuff you have not written yet actually exists, so it really taxes memory and what I'd describe as cache banks. I'd even go as far as saying that it requires a particular mood because one has to put up with this stress.

So far, I've written about 60kb worth of source code. Maybe when I get to 150kb it will become functional. I will probably have to write another 100kb or so after that. We will see how this prediction fares.

In the mean time, as Rodin said, work. Work... and patience.

Fundamentals book

At the request of some folks, there have been some changes to the Fundamentals book. From now on, it will have two parts. The first section will be about Smalltalk programming techniques, and the second one will be about their application in the context of a largish project. Thus, the Fundamentals book will contain the documentation for Assessments.

Assessments 1.0 beta 7

I just published Assessments 1.0 beta 7. It has the following enhancements and fixes.

• SUnitToo is now bridged into Assessments as well. However, note that asking isUnavailable or isAvailable to an SUnitToo test resource which has been stopped will start it again. This currently causes Assessments to detect that a prerequisite failed to stop.
  
• A case of inject: Set new into: [:t :x | t addAll: x such] missing a yourself was detected and fixed. Doh...
• The checklist evaluators got confused when dealing with prerequisite start / stop errors. This has been addressed via polymorphism.

174 classes, 1178 methods, ~6.77 methods / class.

Of the new 8 classes and 22 methods added since the last code change in beta 6, implementing the SUnitToo bridge needed exactly 8 classes and 16 methods. To me, this is just a mere, modest consequence of applying the programming techniques which I have trained myself so hard to use over the last 12 years. Seeing concrete evidence that they make this kind of programming possible, as well as having the chance to watch myself going through the process in a manner similar to that of liquids flowing around obstacles, makes me happy.

The age of cool and lack of accomplishment

Sometimes I can't help thinking we're in an age of cool, or kewl perhaps. Some people have complained about this much more effectively than I could possibly do. However, I'd like to point out the following.

After you get all the gadgets, after you dress fancy and put gel on your hair, after you learn all the buzz words, after you emulate the people you're supposed to emulate because they are shown on TV, and after you decorate what was already known with your own bling, all of this effort and energy spent amounts to no more than a distraction. When this is removed, the truth remains:

The hard thing is to do something that has not been done before.

"I've seen things you wouldn't believe. Attack ships on fire off the shoulder of Orion. I watched C-beams glitter in the dark near the Tanhauser gate. All those moments will be lost in time like tears in the rain... time to die." --- From Philip K. Dick's Do Androids Dream of Electric Sheep, as adapted by the movie Blade Runner.

SUnitToo coming to Assessments

Well, the new SUnitToo bridge just began. Just 5 classes and 11 methods were enough for Assessments to do the following things.

• Become aware of SUnitToo.
• Remap all SUnitToo test cases into Assessment checklists, if SUnitToo is detected.
• Show the remapped test cases in the checklist evaluator.
  
• Execute SUnitToo tests via the Assessments evaluation framework, including handling FailedAssertion properly.

The pending task list is as follows.

• The pragmatized test selectors are not supported yet.
• SUnitToo resources look like they will work, but this has not been verified.
• The hierarchy rules in SUnitToo need to be understood, modeled and implemented as necessary in the test bridge.
• The SomeError exception needs to be researched to see if Assessments needs to handle it as a special case.

But hey --- not bad for 5 classes and 11 methods! Hopefully this trend can be maintained.

Assessments 1.0 beta 6

I just published Assessments 1.0 beta 6. This contains an Assessments fix to SUnit!

What happened was that, in regular SUnit, TestCase class>>shouldInheritSelectors fails because it has no protection against going to ask Object class if it shouldInheritSelectors, which results in a DNU UHE. So I just taught the SUnit bridge in Assessments to treat TestCase specially via subclassing and polymorphism, and now the problem is gone.

Needless to say, SUnit VM did not have this issue.

168 classes, 1156 methods, ~6.88 methods / class.

ESUG 2008 social event RSVP list

If you are attending ESUG, you should add yourself here.

Don't miss out!

Assessments 1.0 beta 4

All bundles and packages have been commented.

Update: I just pushed out beta 5 with a number of comment fixes and enhancements.

Assessments 1.0 beta 2 is now public

I just pushed the publish button, and Assessments 1.0 beta 2 is on its way to the public Store repository. Check out bundle [Assessments]. After it loads, you will see two additions to the Tools menu in the launcher. Any and all feedback is appreciated.

Assessments 1.0 beta 2

I deleted 6 methods that were not necessary. I am having a hard time seeing what else to do.

167 classes, 1153 methods, ~6.90 methods / class.

Fundamentals progress update

I have been writing basically 4-6 pages every day for the last week or so. Perhaps more, I do not remember in full detail as I do not mean to keep track of it.

Chapter 4, On inheritance, now has about 50 pages. I'd say it's about half written. The draft is 166 pages long. Things are moving along just fine.

Another hibernation issue

How about this one? It is extremely irritating indeed. The machine in which it happens is a Dell D820 with 2gb, running Windows XP.

• Start up after hibernation.
• As soon as the "unlock" dialog comes up, try to log back in as fast as possible.
• Make sure you move your USB mouse a lot, too.
  

Then, every so often you get a dialog saying "preparing for hibernation", and the laptop promptly goes to hibernate again. Grrr!!!

Book copies available from a local bookstore

Perhaps you would be interested in having a copy of the mentoring course or the hashing book from a local bookstore? If so, contact the Calico Cat Bookstore.

PS: they currently have a set of signed copies :).

New research project

As it happens, it has become necessary to spend considerable time researching a new field. Everybody knows about it, but I need to take a look at it from a new point of view, in a way in which nobody that I am aware of has seen it before.

The topic is Dilbert.

And while doing the research, I happened to find a fabulous nugget. Amazing, or sad --- your choice.

Hibernation issues

I think I have finally characterized a nasty problem with hibernation. It occurs on two different Windows laptops, with different versions of XP running on them. They are current, patch wise. Here are the steps to reproduce the mess.

1. Have your laptop working with an ethernet network cable attached to it. Make sure traffic can flow through this connection.
   
2. Without disconnecting the ethernet cable first, cause the laptop to hibernate.
3. Then, resume the laptop from hibernation without connecting the ethernet cable.

At this point, the network subsystem may end up thinking it's still connected when it's not. Windows' network management will be hosed. You won't be able to enable / disable WiFi. You won't be able to recover the wireful ethernet network subsystem. Windows will still think the network cable is attached, and sometimes it will show amazing amounts of traffic going by --- with no cable attached, of course (!!!).

At this point you will have to reboot.

Why is this?

Thoughts on SSD drives

I read some lovely stats over at Tom's Hardware showing how truly nice SSD drives are becoming. Not only they can be faster than regular HDD drives... but they can also use far less power, plus they have zero rotational latency and they are basically immune to shocks that would render a regular hard drive useless.

And then... and yet...

According to an article in New Scientist, SSDs can currently be written up to 10,000 times. After that, they lose the capability to store data. So, assuming the new materials referred to are not available for a while, what does that imply for a 64 GB SSD drive like the OCZ one that looks so impressive at Tom's Hardware?

Let's assume we write data to the SSD drive non stop, 24 hours a day. At 100 mb/sec, that's about 10 seconds / gb, and in 640 seconds we fill a 64 gb SSD drive. If we do this 10,000 times, then clearly even the best even wear algorithm will not be able to prevent device failure. So, how long does that take to happen?

64 gb * 10 seconds * 10,000 times / 60 seconds / 60 minutes / 24 hours => ~74 days.

Really. So, this means that in 74 days' worth of writing, an SSD drive stops working. Perhaps earlier due to bad luck, probably earlier due to the even wear algorithm's theoretical inability to do a perfect job. So let's say 60 days for the sake of simplicity.

So here's an interesting statistic I'd like to know now. How much data writing do hard drives do in general? How does the number above compare to what a regular hard drive can do?

For some reason I suspect SSD drives cannot currently compete in the server market. Mind you, a failure in 74 days would mean an MTBF of 1776 hours or less. I really do not see regular hard drives, with their 1+ million hours' worth of MTBF, blowing up after just 2 months of writing operations. And if that is the case, then well... are SSD drives ready for the consumers who are expected to deal with gigabytes of video, software, email, etc?

Maybe the new materials in the New Scientist article change things... until then, I am not so sure that SSDs must be undoubtedly better than regular hard drives in every circumstance.

Normal

"I worked hard. Anyone who works as hard as I did can achieve the same results." --- Johann Sebastian Bach

"One would have to wait and plunder a whole life, if possible a long life; finally, after that, perhaps one would know how to write the ten lines that would be good. This is because verses are not, as some believe, feelings (they are always had too soon)... they are experiences. To write a single verse it's necessary [...] to have lived." --- From "The notebooks of Malte Laurids Brigge", by Rainer Maria Rilke.

"He became silent for a moment and repeated, in a wonderfully serious attitude: 'It is necessary to work, nothing else than to work. And one has to have patience'." --- letter from Rainer Maria Rilke to Clara Rilke, 9/5/1902.

"I did not go to you just to write a study. I arrived to ask you 'How should life be lived?'. And you answered: 'working' [...] what you say: 'work and patience'." --- letter from Clara Rilke to Rodin, 9/11/1902.

To do list...

Now that Assessments reached beta status, I can move on to the next items in my to do list. I am just too tempted now... so I hope you will excuse the (perhaps) obscure cultural reference here.

Lo que sigue lo que sigue en Smalltalk de Primera!...

• The slides for the ESUG presentation need to be made.
• The Smalltalks 2008 Coding Contest needs to be built.
• It would be nice to continue writing the Fundamentals book.
• And I would like, if possible, to sneak in a new surprise talk later in the year.

So much to do --- but it's not my fault that it's so much fun :).

Better get going with it!

Feedback on Assessments

One of the beta testers had very interesting comments regarding Assessments. After a brief introduction, it became obvious to this person that Assessments is much more than it claims to be. In the words of the beta tester,

This is more than a testing tool... this is a general solution to the problem of having a framework running inside another one!

I have a feeling the ESUG talk has a good chance of being interesting. Hopefully it will be well received!

Assessments 1.0 beta

I just finished the last feature still pending for Assessments to reach beta. Everything is done now, all that remains is bugfixing or polishing. There does not seem to be a whole lot of that to do.

Today's exercise clearly shows how truly amazing Assessments is. I mean to say that in all modesty --- I am amazed myself. Here's what happened.

Validation services are a way by which SUnitValidation offers services to other objects. The mechanism involves calling what in SUnit would be called test selectors that take arguments. These are very useful for e.g.: validating UI input on the fly without validating the underlying object. So for example one could have something like

DataEntryValidator>>
validateSomeStringField: theValueOfTheField

and now the task is to run this message with its argument. Note also that this is more than just saying DataEntryValidator new validateSomeStringField:, and that not only the SUnit machinery is at play: validators need the object / originalObject instance variables filled out, and they can cause failures, validation failures and errors just like any other test method. Invoking this feature must result in something that looks like a TestResult.

So here comes Assessments, which was designed only with unary messages in mind instead. There had been zero thought given to sending messages with an argument, or with many arguments. The amount of pain needed to implement this would then be a direct measure of how malleable Assessments is. This is important to me because flexibility in the face of change was one of the design principles behind Assessments. How well did it do?

First, the matter of the arguments was fixed by adding an instance variable called arguments, defaulted to Array new, in a class called ProtectedMessageSend. The class Check is a subclass of this, and therefore all checks inherit the ability to run with arguments. Then, the execution policy objects which dictate exactly how a check is executed changed from this

aCheck actualReceiver
perform: aCheck selector

to this

aCheck actualReceiver
perform: aCheck selector
withArguments: aCheck arguments

Problem solved. Second, the matter of how to create these checks with arguments prefilled was addressed by just a few (meaning two) messages on the class side of ChecklistRepository, and by their instance side counterparts in another class. Strictly speaking, this is not code duplication. I wish I could tell you right now what that unnamed and mysterious class is doing, but its absolutely beautiful functionality will have to wait until ESUG :).

That is it.

And oh by the way, adding an instance variable and on the order of 10 methods (including accessors) is enough for services to become available for the following frameworks:

• Assessments
• Assessments Benchmarks
• Assessments Validation
• Vanilla SUnit running inside Assessments
  
• SUnitVM running inside Assessments
• SUnitBenchmarks running inside Assessments
• SUnitValidation running inside Assessments

All of this, with each selector being treated according to the corresponding execution policy. In other words:

• Checklists (the equivalent of TestCase) do not have testSelector, so they don't use it. They get sent aboutToEvaluateCheck and doneEvaluatingCheck instead of setUp and tearDown.
  
• Validator (the equivalent of AbstractValidator in SUnitVM), a subclass of Checklist, has two instance variables that need to be filled before execution begins.
• Benchmark (the equivalent of AbstractBenchmark in SUnitVM), another subclass of Checklist, uses multiple setUp messages so that each test runs many times in different contexts. Only the setUpXYZ selectors are called scenarioXYZ.
  
• SUnit needs the testSelector prefilled.
• SUnit Validation needs the testSelector and the validation instance variables prefilled.
• SUnit Benchmarks also uses a multiplexing setUp selector mechanism, but of course all the names are different.
  

Never mind that SUnit, SUnitVM and Assessments use different exceptions, or that different execution policies are used to debug and run checks to failure. And never mind that the compatibility of different test selector lookup methodologies is maintained, never mind that no SUnit / SUnitVM code needs to be touched, and never mind that no code is created by Assessments either. All of that is unaffected by this change, as it should be. It may seem self evident, but one thing is to say it and another one is to see it happen as a result of a tiny change.

And the Assessments checklist class that assesses whether this functionality works uses itself as the source of the service.

I think this is a strong confirmation that both the design and the implementation of Assessments is indeed flexible as intended. Thus, it is with happiness that I declare that Assessments is now 100% feature complete and that it has reached beta status.

167 classes, 1159 methods, ~6.94 methods / class.

TwoFinger (apparently) revealed for what it is

I started suspecting that TwoFinger was a particular case of Quicksort. And apparently, it is equivalent to Quicksort in this configuration:

• Center pivot
  
• Two finger partition sorting (efficient when the list is already sorted, every element of the partition is moved exactly once except maybe the pivot, harder to get n^2 cases)
  
• Using R. Sedgewick's idea of recursing on the smallest sublist and using tail recursion for the larger one (efficient use of the stack)

No wonder it was scoring so much better than a less sophisticated Quicksort...

Now, the final details need to be worked out. In particular, how does it compare to VW's hybrid sort as implemented in SortedCollection?...

No

Perhaps this is another post along the lines of Assorted Thoughts, something I have reread a number of times recently. See the thing is I feel weird today, and maybe this makes me see things in a different light at least at this very moment.

I wish I had an invisible video camera. Next to me, there are 5 women watching a video being displayed on a laptop. While they drink their coffees, the narration describes the organization of the clothes department in some mall. The camera follows the lady pointing at signs and grabbing on to things to buy. She says that the focus is on the inside story, with some unrecognizable white item in her hand. The women stare mostly in silence. Certain words are uttered very frequently in the video, in particular "sign", "order" and "register". From a distance, the laptop screen looks like a bunch of colorful squares, something anybody in kindergarden would be able to draw. Then, the ladies laugh at something that seemed funny to them. They all have a rose in their hands --- the flowers are actually pens. There is western music being played in the background. It only makes the situation weirder.

I look to my right. It's almost completely dark. The cloudy sky has only a tinge of blue left. Vangelis' Rachel's Song sounds in my headphones. I feel the urge to do things, and that there is little time left. And yet, I am not in the mood to push today. It should be considered normal, but I find it difficult to accept. I also feel the growing need to leave, as if changing locations was the magic incantation I needed right now. But where should I go next?

I whistle for a bit. I lose interest in that too.

While I look at the ladies do some social game of "please pay attention to me" among themselves, I remember that today I read an article about memristors. There is a photo in the Wikipedia showing a memory circuit in which circuit lines 50 nm thick have been etched. The caption says the lines are 150 atoms wide. A one atom thick line would be 0.3 nm. Intel is about to roll out chips fabricated with a 32 nm process. We're only a factor of 100 away from the end of Moore's Law as far as the miniaturization of current technology circuits is concerned. At a duplication every 18 months, that's about 10 years' worth. I suspect we will hit the wall earlier than that. One of two things are needed: a breakthrough, or a rationalization of what do we spend electricity to figure out.

Which brings me to the ladies. Power from non renewable sources spent to talk about signs, orders, registers, things to buy, the inside story of colorful kindergarden squares... and to manufacture plastic pens in the shape of a rose. Such a sorry state of affairs.

No.

TwoFinger gets another update

So I had run into a problem with TwoFinger. The implementation had a stack usage worst case of n. This means that, in the worst possible scenario, sorting a list of n things would need n stack frames. Totally unacceptable!

Today on the other hand, I am back to happy. Not only I squished the max stack depth to lg n/2 (not even lg n)... I also wrote it in a way that the recursion, if any, causes minimal stack traffic (in terms of message sending context switching, akin to calling functions in C) and stack depth.

This is very nice compared to Quicksort. This is because, if I understand things right, Quicksort will always have to reach a stack depth of lg n/2, if not lg n itself. For TwoFinger, on the other hand, it's only an upper bound. For example, it is not unusual for TwoFinger to sort a list of 1k things using a stack no deeper than 2 or 3 frames.

So now, TwoFinger (in its "2c" incarnation) appears to be generally faster than Quicksort in the following respects.

• Generally less swaps.
• Generally less comparisons.
• Generally less probes.
• Generally less maximum stack depth.
• Generally less stack traffic.

Things are looking good... at least for now. For example, I still do not have a proof of average complexity...

I plan to introduce it in public after my dear beta testers have a chance to go over the details. You may want to consider that I am about to send them a test suite that runs about 500 tests, and a detailed log of performance characteristics of about 140kb, so this may take a bit.

One way or the other, between TwoFinger, the Smalltalks 2008 coding contest and Assessments, the fundamentals book will have original and exciting material in it. For example, it just gained a chapter on recursion...

PS: the test suite for all the sorting algorithms is written in SUnitVM and runs inside Assessments. This is great because then I can leave my legacy tests alone, I get Assessments' much more powerful machinery and tools, and I also get to make use of an Assessments-compatible / Assessments-supported feature set. Adding the measurements for the stack depth and stack traffic, including all the needed reporting aspect of this for the 500 or so tests, was frighteningly easy to do.

Assessments v1.0 alpha 7

The benchmark evaluator is now complete. I did the most beautiful networked sorting objects for it. Only validation services remain before Assessments reaches 1.0 beta.

166 classes, 1138 methods, ~6.86 methods / class.

Assessments v1.0 alpha 6

Today I did the first iteration of the benchmark runner. It was far easier than I had expected. Thanks to the use of refactoring technique, the whole thing was created using less than 40 methods. Now I have a dedicated benchmark tool that can be extended as desired.

157 classes, 1065 methods, ~6.78 methods / class.

TwoFinger update of the day

I did some more work, and I found a way to create a worst case scenario for TwoFinger. The performance is indeed n^2. With some trepidation (I confess) I measured the worst case for TwoFinger with Quicksort, and the worst case for Quicksort with TwoFinger. The result? TwoFinger is significantly more efficient in both cases.

I also tried a set of about 160k random doubles. TwoFinger was more efficient than Quicksort in terms of performed probes (accesses to the collection being sorted), swaps, and object comparisons.

Perhaps there is a remote chance that this is worth the effort.

Maybe. I wonder what the beta testers will say about it.

TwoFinger vs Quicksort

I also did some work on TwoFinger today. I have more than 100 tests with different sequences. None of the 3 varieties of Quicksort that I implemented (left, right and center pivot choice) is more efficient. In fact, I am having serious trouble finding a scenario in which TwoFinger is slower than Quicksort. While this apparent absence of evidence is not definite evidence of absence, the situation just makes me even more curious. There is still one thing I have not tried, and even then it's not clear TwoFinger should be slow (at least to me).

I also proved that TwoFinger is correct. It seems the worst case is not worse than n^2 / 4. The already sorted case, Quicksort's worst case, is extremely fast for TwoFinger. I have no idea of what is the average complexity. It looks like some sort of n log n, but I do not have proof for this yet.

More to come...

Assessments 1.0 alpha 5

I fixed an irritating design problem in the results viewer. I also improved and enhanced the implementation for validation, leaving the door open to any further development along those lines in validation or anywhere else.

150 classes, 1028 methods, ~6.85 methods / class.

Feature wise, only two things remain for Assessments 1.0 to reach beta.

• Explicit support for validation services.
• The serious benchmark runner.

Close, very very close...

Question for today, July 8th 2008

How much space would Earth's atmosphere occupy if it was stored in a sufficiently large vessel at sea level conditions of temperature and pressure? Assume things like gravity do not have an effect, thus the container behaves like a regular balloon.

Update: and if you know this number... how does that compare to the volume of the atmosphere as is now?

Here we go algorithmy again

For some bizarre reason, I had a flash back to 17 years ago when I implemented text sorting in Pascal for a program called GoldOrig (you can still see indirect references to features of GoldOrig being added to similar programs here). What the...

In any case, I remembered that at that point in time I had heard about what was Quicksort, but didn't actually know what it was. Never mind that I had only the most vague of ideas of what the word algorithm meant, I decided I'd figure it out myself. And I ended up doing something I called binary sort, thinking Quicksort was the sorting equivalent of binary (or quick) search.

And well, tonight I got very curious because I remember very well that I had run into difficulty with index management when the pivot for a partition had to be swapped, and that after pulling my hair quite a bit I had found a solution. Of course, I had to implement it again in Smalltalk to see what was going on.

I created an InstrumentedSortAlgorithm that records probes (both at: and at:put:), index swaps, and object comparisons. Then I implemented Quicksort (3 pivot selection varieties), and finally I implemented what today I called TwoFingerBinarySort. I wrote some tests in SUnitVM, ran them with Assessments, and now I was in business because not only I could make sure they ran fine: I could also see exactly what they were doing.

And here comes the interesting part --- I couldn't remember what was the special thing I had come up with when dealing with pivot swaps! So TwoFingerBinarySort was faster only in cases where Quicksort is known to have bad performance, such as when the collection to sort is already sorted.

But after playing with all of this for about 90 minutes I did remember. It also came back as a flash back, the same feeling of "aha!" that I had 17 years ago. I wrote TwoFingerBinarySort2 and... and well... in the 4 test cases I have, either it is extremely close (maybe borderline better by a micron) than Quicksort... or it is way better than Quicksort's pathological cases.

Of course, it must be an issue of test case selection. In other words, most likely what is going on here is that I have not found the pathological tests for TwoFingerBinarySort2 yet, and therefore it looks like it is something to consider. Nevertheless... it makes me really curious... did I just rewrite Quicksort in disguise, or did I actually do something different? What is going on here? And why does it do significantly less work?

One way or the other, I am happy I pulled back what I did 17 years ago from my memory faster than it took me to get to my Pascal source code archive to take a look.

This will continue... probably on the drive home tomorrow :)...

Assessments 1.0 alpha 4

This one adds a copy to clipboard feature to the results viewer so I can share stuff with others over IRC.

Assessments 1.0 alpha 3

Fixed a small bug...

• Handling of SUnitVM notices was slightly incorrect and thus the Assessments based result was built wrong... sigh...

And added a small improvement...

• Some exceptions can be raised without a messageText, for example NoModificationError. For those, use the exception class name instead of the messageText.
  

Enough writing for today

I got on a roll and wrote another 10 pages in 2.5 hours. So, 16 pages were written in 4 hours today. Not bad at all. Also, this seems to indicate that I can write one page every 15 minutes or so when things are going well.

The fundamentals book draft is now 136 pages.

PS: I realized I wrote 26 pages in 2 days, and I have not written much recently. So much for being rusty, I guess (!!!).

More work completed

The fundamentals book gained 6 top quality pages in 90 minutes. I feel a bit drained... I will continue in a little bit. It feels good to have the practice back.

Fundamentals book, chapter 4

Yesterday I found I was a rusty writer, and managed to write only two pages of questionable quality. I was not pleased with myself. Today, on the other hand, I got into the old rhythm again and wrote 8 nice pages in a few hours. I felt much more comfortable, too. Practice is everything.

Chapter 4 is about 25% done. The book draft reached 120 pages.

A small break

I had been concentrating on pretty much the same things for too long... Assessments, the Smalltalks 2008 Coding Contest, number theory, and so on. I needed a break. This is why now I am working on Chapter 4 of the fundamentals book. After a slow start due to my writing being rusty (note to self: do not stop writing for so long), I am now back in business. Everything is going well.

Hashing in Smalltalk, exercise 5.3

Working with Dan D'Eramo on this problem suggests that the hash function f follows a Poisson distribution, in which case its variance is equal to the mean of the values of f. This appears to solve exercise 5.3 satisfactorily. I will be working to rewrite the (currently) vague solution given in the book using this new information.

If all holds, then this might provide an actual definition of what a good quality hash function is.

Assessments v1.0 beta feature list

So now that v1.0 alpha is done, it's time to think about the v1.0 beta features. There are only three such things.

• Explicit support for validation services.
• Comparison validation.
  
• A serious benchmark evaluator.

The first two should be easy to do. The last one, however, will require significant thought.

Assessments v1.0 alpha

Assessments has reached 1.0 alpha 1. This means it's feature complete as per the 1.0 spec: it provides all the major features of SUnit / SUnitVM, it is able to run existing SUnit / SUnit VM tests (and benchmarks and validators) without causing code change to occur to existing tests, and its design is oriented towards flexibility for future enhancements.

• 148 classes.
• 1008 methods.
• ~6.81 methods per class on average.

I will ship this code base to the beta testers du jour, and start working on the final annoyances that are left. I am basically done. I can't believe it.

Update: an additional method fixes the only known annoyance in this source code base, thus making 1.0 alpha 2.

• 148 classes.
• 1009 methods.
• ~6.82 methods per class on average.
  

Vacation, eh?

Sure, why not... let's go out to the wilderness and don't do anything for a while. And yet, I knew I was lying to myself. I predicted I wouldn't last even 3 days before I'd be compelled to go create new things.

Indeed. Today for example. I had been doing little things in the last 2 days, and the stuff ready for coding piled up quickly. Yesterday I had a design session for the Smalltalks 2008 coding contest, and this caused even more implementation details to appear out of thin air. All of this material is going to my queue of things to do, and now I cannot take this anymore. I need to finish Assessments and push the size of the queue back down. Hopefully I'll be done within the next 4 hours. We'll see how it goes...

Update A1: 130 minutes later, Assessments has native validation facilities. Next up, the SUnit Validation bridge. 148 classes, exactly 1000 methods, ~6.76 methods / class.

Update A2: a few minutes later, some refactoring, cleanup and bug fixes resulted in the overall deletion of one method. 148 classes, 999 methods, 6.75 methods / class.

Update B: 25 minutes after update A1, some 165 minutes since I started, Assessments runs existing validators successfully. What's funny is that the assessment checklist uses the bridged validator to run the tests :). Some small issues remain, but it's nothing serious.

Anatolii Karatsuba meets Leonardo de Pisa

In the posts regarding Fibonacci, it came up that the VisualWorks' large integer multiplication primitive isn't the most suitable to calculate products of truly huge numbers. In this case, the term "truly huge" refers to numbers which can easily have one million bits, so they are way beyond what would be considered normal usage. And nevertheless...

I looked around and found Karatsuba's algorithm for multiplication. While it would be nice to put it in the VM, it is also possible to implement it in the image by letting it use the existing primitive when the number sizes are suitable for it.

After a bit of massaging the implementation, which is not the most efficient one because again this should be in the VM or otherwise in C, I got Karatsuba to tie the VM's performance at about 2k bits. Here are some measurements after that.

• 3k bits: Karatsuba 12% faster than the VM.
• 4k bits: Karatsuba 6% faster than the VM.
• 8k bits: Karatsuba 33% faster than the VM.
• 16k bits: Karatsuba 31% faster than the VM.
• 64k bits: Karatsuba 2.51x faster than the VM.
• 256k bits: Karatsuba 3.96x faster than the VM.
• 1m bits: Karatsuba 8.85x faster than the VM.

So I subclassed the F(a+b) Fibonacci calculator so that it uses Karatsuba instead of regular multiplication. Result?

• 1953152 fibonacci: Karatsuba F(a+b) 4.38x faster than the regular F(a+b) calculator.

How about that...

SmallInteger>>karatsubaTimes: anInteger

^anInteger * self

LargeInteger>>karatsubaTimes: aLargeInteger

| splitThreshold
selfHigh selfLow aLargeIntegerHigh aLargeIntegerLow
highProduct lowProduct mixedProduct lowTerm |
self digitLength + aLargeInteger digitLength > 768
ifFalse: [^self * aLargeInteger].
splitThreshold := self digitLength
+ aLargeInteger digitLength
* 2.
selfHigh := self bitShift: splitThreshold negated.
selfLow := self - (selfHigh bitShift: splitThreshold).
aLargeIntegerHigh := aLargeInteger
bitShift: splitThreshold negated.
aLargeIntegerLow := aLargeInteger
- (aLargeIntegerHigh bitShift: splitThreshold).
highProduct := selfHigh karatsubaTimes: aLargeIntegerHigh.
lowProduct := selfLow karatsubaTimes: aLargeIntegerLow.
mixedProduct := selfLow + selfHigh karatsubaTimes:
aLargeIntegerLow + aLargeIntegerHigh.
lowTerm := mixedProduct - (lowProduct + highProduct).
^((highProduct bitShift: splitThreshold)
+ lowTerm bitShift: splitThreshold)
+ lowProduct