Faster Decimal to Binary Function

There was recently a post on the Oracle forums by a person who needed to convert decimal values to a binary string. They had found the standard library PL/SQL function that you often see on Oracle sites, but its slow performance was giving him headaches. It was an interesting thread as many people offered solutions, and it showed the ingenuity of people, in coming up with alternatives. In this article I’ll show some of my efforts, and my final function which, to my pleasure, was the fastest in the thread.

Note: During these tests I won’t be using result caching / deterministic clauses / pragma udf options, that can be used on functions – as some of these are Oracle version specific. In reality I probably would use these.

The Standard Approach

The standard approach to this problem is to use DIV (integer division) and MOD ( modulo – i.e. the remainder after division of one number by another).

Note : Oracle has a MOD function and DIV is provided by trunc(value / divisor).
So given an input, you loop whilst not zero and keep MOD-ing by 2 (which will yield a 1 or 0 remainder) adding to the string, then you DIV the current total by two and continue.

Here’s the code. I’ll call it dec2bin_std and will be giving other routines a unique name, as we’ll be comparing performance of different approaches and it will enable us to distinguish the variants.

create or replace function dec2bin_std(pDecimal      in number,
                                       pNumberOfBits in number default null) return varchar2 is
  vResult  varchar2(64);
  vDecimal number := pDecimal;
begin
  if pDecimal is not null then
    while (vDecimal > 0)
    loop
      vResult  := mod(vDecimal, 2) || vResult;
      vDecimal := trunc(vDecimal / 2);
    end loop;
    if pNumberOfBits is not null and pNumberOfBits > length(vResult) then
      vResult := lpad(vResult, pNumberOfBits, '0');
    end if;
  end if;
  return vResult;
end;

Paulzip’s Hex Approach (case statement lookup)

I remembered from some course at university that hex to binary was a lot easier as you could simply process each hex digit (a nibble or half a byte) into a looked up 4 digit binary block and append to the binary string. I suspected this would be a quicker operation than MOD / DIV approach which does a single bit each iteration, as it was doing 4 bit operations at once (1 hex digit = 1 nibble = 4 bits). You can convert decimal to hex using to_char(… ‘fmxxxxxxxx’) (fm removes preceding whitespace and x is the format mask for hex digit), and as to_char was written by Oracle in C and is highly optimised and performant, I thought this approach was bound to be quicker.

create or replace function dec2bin_hex_case(pDecimal in number, 
                                            pNumberOfBits in number default null) return varchar2 is
  vHex varchar2(20);
  vResult varchar2(64);
begin
  if pDecimal is not null then
    vHex := to_char(pDecimal, 'fmxxxxxxxxxx');
    for n in 1..length(vHex)
    loop
      vResult := vResult ||
       case substr(vHex, n, 1)
         when '0' then '0000'
         when '1' then '0001'
         when '2' then '0010'
         when '3' then '0011'
         when '4' then '0100'
         when '5' then '0101'
         when '6' then '0110'
         when '7' then '0111'
         when '8' then '1000'
         when '9' then '1001'
         when 'a' then '1010'
         when 'b' then '1011'
         when 'c' then '1100'
         when 'd' then '1101'
         when 'e' then '1110'
         when 'f' then '1111'
       end;
    end loop;
    if pNumberOfBits is not null and pNumberOfBits > length(vResult) then
      vResult := lpad(vResult, pNumberOfBits, '0');
    end if;    
  end if;
  return vResult;
end;

Performance Test

Someone on the original, did some timings (PL/SQL and SQL) and so I will be doing the same.  I’ll loop through the first million positive decimals in SQL and PL/SQL and do some timing.  To avoid optimiser shortcuts, in SQL I’ll get Oracle to find the max value. All timings are in seconds.

PL/SQL

declare  
  vBinary varchar2(64);
  vStart integer := 1;
  vEnd   integer := 1000000;
  vTimer number;
  procedure LogTime(pDesc varchar2 default null) is
  begin
    if pDesc is not null then
      DBMS_OUTPUT.PUT_LINE (pDesc ||' = '||to_char(dbms_utility.get_time - vTimer) / 100);
    end if;
    vTimer := dbms_utility.get_time;    
  end;  
begin
  LogTime;  
  for i in vStart..vEnd 
  loop  
    vBinary := dec2bin_std(i);  
  end loop;
  LogTime('dec2bin_std');
---------
  for i in vStart..vEnd 
  loop  
    vBinary := dec2bin_hex_case(i);  
  end loop;
  LogTime('dec2bin_hex_case');               
end;

dec2bin_std      = 14.61
dec2bin_hex_case =  6.15

--My hex approach in PL/SQL is 57.91% faster.

SQL

select max(val)
from (  
  select dec2bin_std(level) val  
  from dual
  connect by level <= 1000000  
);

24.71 seconds

select max(val)
from (  
  select dec2bin_hex_case(level) val  
  from dual
  connect by level <= 1000000  
);

17.03 seconds

-- My hex approach in SQL is 31.08% faster.

Note : The SQL solution took longer because of the sort involved in finding the max

Further Improvements

OK, so the hex approach is considerably faster, so seems to be the way forward.  In the thread someone suggested using if statements for the nibble lookup rather than case statements, as ifs are processed faster.

I also wondered if there was a faster way to look up the binary equivalent to the hex digit, so I’ve included some of my attempts.

create or replace function dec2bin_hex_if(pDecimal in number, 
                                          pNumberOfBits in number default null) return varchar2 is  
  vHex varchar2(20);  
  vResult varchar2(64);  
  vHexDigit varchar2(1);  
begin  
  if pDecimal is not null then  
    vHex := to_char(pDecimal, 'fmxxxxxxxxxx');  
    for n in 1..length(vHex)  
    loop  
      vHexDigit := substr(vHex, n, 1);     
      if vHexDigit = '0' then   
        vResult := vResult || '0000';    
      elsif vHexDigit = '1' then   
        vResult := vResult || '0001';       
      elsif vHexDigit = '2' then   
        vResult := vResult || '0010';       
      elsif vHexDigit = '3' then   
        vResult := vResult || '0011';                                                                         
      elsif vHexDigit = '4' then   
        vResult := vResult || '0100';                                                                         
      elsif vHexDigit = '5' then   
        vResult := vResult || '0101';                                                                         
      elsif vHexDigit = '6' then   
        vResult := vResult || '0110';                                                                         
      elsif vHexDigit = '7' then   
        vResult := vResult || '0111';                                                                         
      elsif vHexDigit = '8' then   
        vResult := vResult || '1000';                                                                         
      elsif vHexDigit = '9' then   
        vResult := vResult || '1001';                                                                         
      elsif vHexDigit = 'a' then   
        vResult := vResult || '1010';                                                                         
      elsif vHexDigit = 'b' then   
        vResult := vResult || '1011';                                                                         
      elsif vHexDigit = 'c' then   
        vResult := vResult || '1100';                                                                         
      elsif vHexDigit = 'd' then   
        vResult := vResult || '1101';                                                                         
      elsif vHexDigit = 'e' then   
        vResult := vResult || '1110';                                                                         
      elsif vHexDigit = 'f' then   
        vResult := vResult || '1111';  
      end if;  
    end loop;  
    if pNumberOfBits is not null and pNumberOfBits > length(vResult) then  
      vResult := lpad(vResult, pNumberOfBits, '0');  
    end if;      
  end if;  
  return vResult;  
end;

create or replace function dec2bin_arr(pDecimal in number, 
                                       pNumberOfBits in number default null) return varchar2 is
  type TBinLookup is varray(16) of varchar2(4);
  vBinLookup TBinLookup;
  vHex varchar2(20);
  vResult varchar2(64);
  vHexDigit varchar2(1);
begin
  if pDecimal is not null then
    vHex := to_char(pDecimal, 'fmxxxxxxxxxx');
    vBinLookup := TBinLookup('0000', '0001', '0010', '0011',
                             '0100', '0101', '0110', '0111',
                             '1000', '1001', '1010', '1011',
                             '1100', '1101', '1110', '1111');
    for n in 1..length(vHex)
    loop
      vHexDigit := substr(vHex, n, 1);
      vResult := vResult || vBinLookup(case when vHexDigit in ('a', 'b', 'c', 'd', 'e', 'f') then 
                                         ascii(vHexDigit) - 87
                                       else
                                         to_number(vHexDigit)
                                       end + 1);
    end loop;
    if pNumberOfBits is not null and pNumberOfBits > length(vResult) then  
      vResult := lpad(vResult,pNumberOfBits,'0');  
    end if;      
  end if;
  return vResult;  
end;


create or replace function dec2bin_hex_slice(pDecimal in number, 
                                             pNumberOfBits in number default null) return varchar2 is
  vBinLookup constant varchar2(64) := '0000000100100011010001010110011110001001101010111100110111101111';
  vHex varchar2(20);
  vResult varchar2(64);
begin
  if pDecimal is not null then
    vHex := to_char(pDecimal, 'fmxxxxxxxxxx');
    for n in 1..length(vHex)
    loop
      vResult := vResult || substr(vBinLookup, (instr('0123456789abcdef', substr(vHex, n, 1)) * 4) - 3, 4);
    end loop;
    if pNumberOfBits is not null and pNumberOfBits > length(vResult) then  
      vResult := lpad(vResult, pNumberOfBits, '0');  
    end if;      
  end if;
  return vResult;  
end;

create or replace function dec2bin_hex_slice2(pDecimal in number, 
                                              pNumberOfBits in number default null) return varchar2 is
  vBinLookup constant varchar2(64) := '0000000100100011010001010110011110001001101010111100110111101111';
  vHex varchar2(20);
  vResult varchar2(64);
  vHexDigit varchar2(1);
begin
  if pDecimal is not null then
    vHex := to_char(pDecimal, 'fmxxxxxxxxxx');
    for n in 1..length(vHex)
    loop
      vHexDigit := substr(vHex, n, 1);    
      vResult := vResult || substr(vBinLookup, (case when vHexDigit in ('a', 'b', 'c', 'd', 'e', 'f') then 
                                                  ascii(vHexDigit) - 87
                                                else
                                                  to_number(vHexDigit)
                                                end * 4) - 3, 4);
    end loop;
    if pNumberOfBits is not null and pNumberOfBits > length(vResult) then  
      vResult := lpad(vResult,pNumberOfBits,'0');  
    end if;      
  end if;
  return vResult;  
end;
  
create or replace function dec2bin_hex_slice3(pDecimal in number, 
                                              pNumberOfBits in number default null) return varchar2 is
  vBinLookup constant varchar2(100) := '0000000100100011010001010110011110001001101010111100110111101111';
  vHex varchar2(20);
  vResult varchar2(64);
begin
  if pDecimal is not null then
    vHex := to_char(pDecimal, 'fmxxxxxxxxxx');
    for n in 1..length(vHex)
    loop
      vResult := vResult || substr(vBinLookup, (to_number(substr(vHex, n, 1), 'fmx') * 4) - 3, 4);
    end loop;
    if pNumberOfBits is not null and pNumberOfBits > length(vResult) then  
      vResult := lpad(vResult,pNumberOfBits,'0');  
    end if;      
  end if;
  return vResult;  
end;

-- All PLSQL Results
dec2bin_std        = 14.61
dec2bin_hex_case   =  6.34
dec2bin_hex_if     =  4.35
dec2bin_arr        = 14.64
dec2bin_arr2       = 12.41
dec2bin_hex_slice  =  3.82
dec2bin_hex_slice2 =  6.00
dec2bin_hex_slice3 =  4.94

-- All SQL Results
dec2bin_std        = 24.71
dec2bin_hex_case   = 17.28
dec2bin_hex_if     = 14.81
dec2bin_arr        = 26.01
dec2bin_arr2       = 23.91
dec2bin_hex_slice  = 14.81
dec2bin_hex_slice2 = 17.53
dec2bin_hex_slice3 = 15.86

The winner is dec2bin_hex_slice, here’s the performance improvements over dec2bin_std
PL/SQL : 73.85% decrease
SQL : 40.06% decrease

Note : The SQL performance improvement is a bit deceptive, as the sorting of a million values for the max operation would be a contributing factor and probably a percentage of the operating time, the PL/SQL improvement is much more accurate reflection of improvement.

The Fastest Decimal To Binary Function

Here’s the fastest Decimal to Binary routine, it outperforms the standard routine considerably. I’ve renamed it dec2bin so it’s ready to use.

create or replace function dec2bin(pDecimal in number, 
                                   pNumberOfBits in number default null) return varchar2 is
  vBinLookup constant varchar2(64) := '0000000100100011010001010110011110001001101010111100110111101111';
  vHex varchar2(20);
  vResult varchar2(64);
begin
  if pDecimal is not null then
    vHex := to_char(pDecimal, 'fmxxxxxxxxxx');
    for n in 1..length(vHex)
    loop
      vResult := vResult || substr(vBinLookup, (instr('0123456789abcdef', substr(vHex, n, 1)) * 4) - 3, 4);
    end loop;
    if pNumberOfBits is not null and pNumberOfBits > length(vResult) then  
      vResult := lpad(vResult, pNumberOfBits, '0');  
    end if;      
  end if;
  return vResult;  
end;

Some Notes

  • vBinLookup holds the binary values from 0 to 15 concatenated together.
  • instr(‘0123456789abcdef’, substr(vHex, n, 1)) converts a hex digit into decimal, by using the position of the hex digit in the hex list ‘0123456789abcdef’.  We use this to lookup the binary equivalent of the hex digit, in vBinLookup by multiplying by 4 and deducting 3.
  • Results can have leading 0s, if this is undesirable, simply add ltrim(vResult, ‘0’) to the function
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s