I've now got two things that I want to talk about; one is technical and the other is about cooking.
On to the technical. I'll blog the cooking in another entry.
Just recently at work I had cause to revisit an old technique that I hadn't used in years and I thought that it would be worth recording here.
We've been working with small binary fields in the database containing information that needs to be parsed. So far within the system we have kept much of the data-centric heavy lifting within the database but we were having difficulty with the binary information. The database provided a set of procedures for manipulating the binary information, but they were not very efficient. They were designed to work with extremely large pieces of binary information and tended to keep the binary information out of memory and in the database.
In general the database was far more designed to work with strings.
The work around was one that had been used when binary information needed to be manipulated by string-centric languages in the past. We converted the binary into a hexadecimal string. This allowed us to make use of in-memory string datatypes, and all the very efficient string manipulation tools that the database made available to us (but with the offsets doubled!). In this case we were fortunate as the database was able to do direct conversions from hex into numbers and then perform AND operations on the numbers as needed.
If that capability hadn't been there we could have used a further technique: to do a fast AND from hex you just build a look up table. The table provides a look up between the two hex values that you want to AND. For example a look up table that does just one hex digit at at time would look like:
| HEX - AND | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 2 | 0 | 0 | 2 | 2 | 0 | 0 | 2 | 2 | 0 | 0 | 2 | 2 | 0 | 0 | 2 | 2 |
| 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 |
| 4 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | 4 |
| 5 | 0 | 1 | 0 | 1 | 4 | 5 | 4 | 5 | 0 | 1 | 0 | 1 | 4 | 5 | 4 | 5 |
| 6 | 0 | 0 | 2 | 2 | 4 | 4 | 6 | 6 | 0 | 0 | 2 | 2 | 4 | 4 | 6 | 6 |
| 7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 |
| 9 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 8 | 9 | 8 | 9 | 8 | 9 | 8 | 9 |
| A | 0 | 0 | 2 | 2 | 0 | 0 | 2 | 2 | 8 | 8 | A | A | 8 | 8 | A | A |
| B | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 8 | 9 | A | B | 8 | 9 | A | B |
| C | 0 | 0 | 0 | 4 | 0 | 0 | 0 | 4 | 8 | 8 | 8 | C | 8 | 8 | 8 | C |
| D | 0 | 1 | 0 | 1 | 4 | 5 | 4 | 5 | 8 | 9 | 8 | 9 | C | D | C | D |
| E | 0 | 0 | 2 | 2 | 4 | 4 | 6 | 6 | 8 | 8 | A | A | C | C | E | E |
| F | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
If you don't mind sacrificing more memory a 2 hex digit or greater lookup table can be created and of course a lot of the time you can distill the lookup further as you only need to do a single bit mask operation and so you would only need on one axis 1,2,4,8 etcetera.
By turning the binary manipulation into a hexadecimal one, we managed to increase the performance by 500%. Of course for really heavy binary manipulation you can't beat a binary friendly language but this technique can be an useful 'good enough' solution.
1 comment:
Bob, To be honest, I didn't read all of this artical, because it brought back thoughts of my Uncle John Tyler Inscoe. If you could have chosen a Dad that man would have been mine. He passed away in 2004 and I miss him. Anyway, my Uncle John was one of the first computer program writers in America in the days when a computer took up a whole room. He took me there once to see all the spinning things, I was six... as I stood infront of this large wall size thing he looked down at me and said one day I shall prove to you that 1+1 = 1 It has stuck in my head all my life and never did he get the chance to explain this strange concept that he and (as the story goes) another friend in the Korean war where working on. As he has now passed away I am still left, that little six year old wondering how could it be, so I ask you, one day to explain to me why my Uncle John was right and all my teachers where nutts! Love ya, tamara
Post a Comment