Blaine Buxton: Positronic Vibrations

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!

Labels: design, programming, ruby

posted by Blaine at 5:50 PM |  0 comments |  Post a Comment

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!

Labels: design, programming, ruby

posted by Blaine at 12:20 AM |  2 comments |  Post a Comment

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.

Labels: misc

posted by Blaine at 8:57 PM |  0 comments |  Post a Comment

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.

Labels: smalltalk

posted by Blaine at 6:56 PM |  3 comments |  Post a Comment