Tuesday, August 28, 2007

String Concatenation

I made a small mistake in the code in "Promises and String Concatenation". The DelayString object not being stateless is a huge problem. Here's the test to prove it:
    def test_independence
first = "3" + "4"
second = first + "5"
third = "2" + second
assert_equal("34", first.to_s)
assert_equal("345", second.to_s)
assert_equal("2345", third.to_s)
end

Ouch. I fixed it by making DelayString only know a left and a right part. It cleaned the code up quite a bit. I factored out Promise because it made the code a little less readable. The resulting code is much simpler:
class DelayString

def initialize(oneString, anotherString)
@left = oneString
@right = anotherString
end

def +(another)
DelayString.new(self, another)
end

def to_s()
return @result unless @result.nil?
to_process=[self]
@result=String.stream_contents do |out|
until (to_process.empty?)
current=to_process.pop
current.process(to_process,out)
end
end
end

def process(to_process,io)
to_process.push(@right)
to_process.push(@left)
end

end



class String

def self.stream_contents(&monadic)
StringIO.open() do |io|
monadic.call(io)
io.string
end
end

def +(another)
DelayString.new(self, another)
end

def process(to_process,io)
io << self
end

end

All of our tests run. DelayString is stateless (minus caching of the result). There's still improvements to be made, but the code is simpler and easier to understand. The performance did take a hit. It's twice as slow (43.94s) as the previous version. Not to worry it still beats normal concatenation by a large margin. I'll take the performance hit for more readable code anyday!

Saturday, August 25, 2007

Promises And String Concatenation

You've read about it a million times. Beware of multiple string concatenations. They make your code slow and consumes memory. You've read it in the Java books (known as "use StringBuilder or StringBuffer instead of +"). But, why? Why isn't this handled at a lower level? Why can't the VM or compiler just do the right thing?

Messages are the power of objects. So, why not make a new object that when sent the + message, it simply returns an object that waits to do the concatenation until it is needed. This new kind of object should understand the same protocol as string. This could all be handled underneath the covers. If it was done at the VM or compiler level, programmers would never have to know.

I thought I would do a sample implementation. It's rather easy (in a dynamic language). First, we need to implement a Promise class and here's the Ruby code complete with a simple test:
require 'rubyunit'

class Promise
def initialize(&block)
@calculation=block
@value=nil
end

def value
return @value if @calculation.nil?
@value=@calculation.call()
@calculation=nil
freeze()
return @value
end

def value?
@calculation.nil?
end
end

def promise(&block)
Promise.new(&block)
end

class PromiseTest < Test::Unit::TestCase
def test_simple
promise = promise { 3 + 4 }
assert(!promise.value?)
assert(7 == promise.value)
assert(promise.value)
end
end

Pretty simple, huh? Create a new Promise object on a block (or closure or lambda or whatever you like to call it) and it will only call the block once when the message "value" is sent to it. If the message "value" is never sent, the block is never evaluated. Can you think where that might come in handy? I can think of several, but the best one is when trying to create a message to log. If you don't log the message, you wouldn't need to do the concatenation. Again, not doing the computation upfront can not only allow us to manage memory better, but also not to do needless calculations.

Enough talk, let's get to the good stuff, right? Here's my implementation of delaying concatenations and check the tests out at the bottom:
require 'stringio'

class DelayString
def initialize(oneString, anotherString)
@strings = [oneString, anotherString]
@promise = promise do
stream = @strings.inject(StringIO.new) do |output,each|
output << each
end
@strings = nil
freeze()
stream.rewind
stream.read
end
end

def +(another)
return another.concatBeforeDelayString(self)
end

def concatBeforeString(another)
@strings.unshift(another)
self
end

def concatAfterString(another)
@strings.push(another)
self
end

def concatBeforeDelayString(another)
strings_each do |each|
another.concatAfterString(each)
end
another
end

def concatAfterDelayString(another)
another.concatBeforeDelayString(self)
end

def to_s()
@promise.value()
end

private
def strings_each(&block)
@strings.each(&block)
end

end

class String
def +(another)
return another.concatBeforeString(self)
end

def concatBeforeString(another)
another.concatAfterString(self)
end

def concatAfterString(another)
DelayString.new(self, another)
end

def concatBeforeDelayString(another)
another.concatAfterString(self)
end

def concatAfterDelayString(another)
another.concatBeforeString(self)
end
end

class DelayStringTest < Test::Unit::TestCase
def test_simple
add = "3" + "4"
assert_equal("34", add.to_s)
end

def test_string
add = "3" + "4"
add = "2" + add
add = add + "5"
assert_equal("2345", add.to_s)
end

def test_delay
add_before = "1" + "2"
add_after = "3" + "4"
add = add_before + add_after
assert_equal("1234", add.to_s)
#make sure to get same answer twice
assert_equal("1234", add.to_s)
end
end

One new class called DelayString handles not doing the concatenation until absolutely necessary. It does this by creating a Promise that calculates the string by using a StringIO object (Stream or StringBuilder in Java terms). All it does is keeps a collection of all the strings it needs to append to one another. The power is now that we get the nice succinct message "+" and all of the benefits of using a stream object (or StringBuilder). Of course, we would need to add more methods on our DelayString so that it has the same protocol as String. A little more work to make our implementation seamless.

Below is the test method I added to find the times it took to run for delayed and normal concatenation:
    def test_performance
add = ''
1000000.times do |iteration|
add = add + 'a'
end
add.to_s
end

The new delayed implementation ran at 23.8 seconds. Not bad to do a million additions and a lot of little ones at that. Now, what were the results the old way? Well, all you have to do is comment out the + message:
#  def +(another)
# return another.concatBeforeString(self)
# end

It took 4565.68 seconds to run the normal way. It performed poorly and took up a bunch of memory. Yuck. It's what the books warned us about right? It's what we expected somewhat. I didn't expect how much of a performance gain I really got. Pretty cool, huh? Amazing.

It's unlikely that we'll do something to this extreme in the real world. But, wouldn't it be nice to not worry about performance in our regular code? If we find that our implementation is sub-par, one of the new benefits is that we can change it in one place.

Wait a minute. We just got better performance and got to keep the simple way of doing things? Not one lick of our already existing code had to change. The power of messages is powerful indeed!

Saturday, August 18, 2007

Quiet Lately

It's been a busy couple of months for me. I've been giving a bunch of talks (Refactoring, Good APIs, and Design). Switched from being a consultant to an employee working for an incredible team. I spent two weeks traveling and to top it off, I saw some of my fave artists (Alice Cooper, Behemoth, and Shadow's Fall) and caught a late summer cold. Still recovering from the cold and trying to get back into blogging. Sorry for being so quiet, I plan to correct that situation soon. Life is getting back to normal. I just got to kick this cold.

Saturday, August 11, 2007

My Favorite Smalltalk is Gone

I am so sad. I come back from seeing one of my favorite artists only to read sad news. I can not express how much I enjoyed working in Dolphin and using it. I was a proud supporter and was always excited to see a new version. This really sucks. Dolphin had the best Smalltalk period. In fact, it's the one I used to get people hooked. It looked modern and was extremely easy to use.

I realize it's hard to make money in the software development tools business. My own business failed as well. I was hoping for Dolphin to stick it out. Good luck to the Dolphin guys. I just want to thank them for all the love they put into the world. Dolphin will always have a special place in my heart. It will be hard to say good-bye.

Well, there's no reason for me to stay with Windows anymore now.

Amazon