Menu
I am writing an immutable DOM tree in Java, to simplify access from multiple threads.*
However, it does need to support inserts and updates as fast as possible. And since it is immutable, if I make a change to a node on the N'th level of the tree, I need to allocate at least N new nodes in order to return the new tree.
My question is, would it be dramatically faster to pre-allocate nodes rather than create new ones every time the tree is modified? It would be fairly easy to do - keep a pool of several hundred unused nodes, and pull one out of the pool rather than create one whenever it was required for a modify operation. I can replenish the node pool when there's nothing else going on. (in case it isn't obvious, execution time is going to be much more at a premium in this application than heap space is)
Is it worthwhile to do this? Any other tips on speeding it up?
Alternatively, does anyone know if an immutable DOM library already? I searched, but couldn't find anything.
*Note: For those of you who aren't familiar with the concept of immutability, it basically means that on any operation to an object that changes it, the method returns a copy of the object with the changes in place, rather than the changed object. Thus, if another thread is still reading the object it will continue to happily operate on the "old" version, unaware that changes have been made, rather than crashing horribly. See http://www.javapractices.com/topic/TopicAction.do?Id=29
207
Memory usage of some typical Java objects Theoretically, a long requires 4 more bytes compared to an int. But because object sizes will typically be aligned to 8 bytes, a boxed Long will generally take up 24 bytes compared to 16 bytes for an Integer.
Minimum object size is 16 bytes for modern 64-bit JDK since the object has 12-byte header, padded to a multiple of 8 bytes. In 32-bit JDK, the overhead is 8 bytes, padded to a multiple of 4 bytes.
In computer science, overhead is any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to perform a specific task.
The class takes up at least 8 bytes. So, if you say new Object(); you will allocate 8 bytes on the heap. Each data member takes up 4 bytes, except for long and double which take up 8 bytes. Even if the data member is a byte, it will still take up 4 bytes!
These days, object creation is pretty dang fast, and the concept of object pooling is kind of obsolete (at least in general; connection pooling is of course still valid).
Avoid premature optimization. Create your nodes when you need them when doing your copies, and then see if that becomes prohibitively slow. If so, then look into some techniques to speed it up. But unless you already know that what you've got isn't fast enough, I wouldn't go introducing all the complexity you're going to need to get pooling going.
171
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
