GNU logs - #14158, boring messages

Message sent to bug-coreutils@HIDDEN:

Subject: bug#14158: Base64 -d is slow
Resent-From: Ole Tange <ole@HIDDEN>
Original-Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Resent-CC: bug-coreutils@HIDDEN
Resent-Date: Mon, 08 Apr 2013 07:39:02 +0000
Resent-Message-ID: <handler.14158.B.136540669825210 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: 14158 <at> debbugs.gnu.org
MIME-Version: 1.0
From: Ole Tange <ole@HIDDEN>
Date: Mon, 8 Apr 2013 09:26:04 +0200
Message-ID: <CA+4vN7woWZBJ7aKHnxBADP=WjmMRJMn21sO1msadBwO+M3kWYg@HIDDEN>
Content-Type: text/plain; charset=ISO-8859-1
Precedence: list
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org

I was astonished to learn that:

  perl -MMIME::Base64 -e 'while(read(STDIN,$buf,770*50)){print
decode_base64($buf)}'

is faster than:

  base64 -d

My C-skills are quite limited, but it seems the current implementation
does a lot of computation and not table lookups.

Below are my thoughts on how this could be improved.

/Ole

= Designing a fast Base64 decoder =

By: Ole Tange <tange@HIDDEN>

== Goal ==

We want something that is parallelizable since that can take advantage of:

* Multiple cores/CPUs
* Vector processing (MMX/SSE)
* Processors with pipelines

== Observations ==

In Base64 every 4 bytes represent 3 bytes of decoded information.

Binary input: aaaaaaaa bbbbbbbb cccccccc dddddddd
=>
Base64 index: 111111 222222 333333 444444
=>
Decoded: 11111122 22223333 33444444

Given input byte 1 and 2 we can determine output byte 1.

Given input byte 2 and 3 we can determine output byte 2.

Given input byte 3 and 4 we can determine output byte 3.

A way to make an algorithm parallelizable is by not making
computations based on previous results, but only base the computation
on the input.

== Idea ==

Make a lookup table for the output byte.

By making a 16-bit lookup table for the first 2 bytes, the middle 2
bytes and the last 2 bytes, conversion of 4 byte to 3 bytes is fast
and independent of previous computations.

The lookup table can also deal with the conversion to Base64 index -
thus skipping this step. It can even deal with all the non-conflicting
variations of which char codes for index 62 and 63.

  out_byte1 = first[in_byte1][in_byte2];
  out_byte2 = middle[in_byte2][in_byte3];
  out_byte3 = last[in_byte3][in_byte4];

Each lookup table will at most be 64kbytes = 192kbytes total.

== Implementation ==

Here is the implementation in pseudo code:

byte compute_first_byte(int i, int j) {
  /* Return the decoded value of the first byte, given the first 2
bytes are i and j */
}

byte compute_middle_byte(int i, int j) {
  /* Return the decoded value of the middle byte, given the middle 2
bytes are i and j */
}

byte compute_last_byte(int i, int j) {
  /* Return the decoded value of the last byte, given the last 2 bytes
are i and j */
}

/* Lookup tables */
static byte first[256][256];
static byte middle[256][256];
static byte last[256][256];
static bool already_computed = 0;

void decode(byte* in, int len, byte* out) {
  /* in = pointer to input bytes with no garbage (\n and similar)
     len = length of input (must in 4 byte blocks)
     out = pointer to output buffer of length 3/4*len
  */

  /* Initialize lookup tables */
  if(! already_computed) {
    parallel_for(int i = 0; i < 256; i++) {
      parallel_for(int j = 0; j < 256; j++) {
        first[i][j] = compute_first_byte(i,j);
        middle[i][j] = compute_middle_byte(i,j);
        last[i][j] = compute_last_byte(i,j);
      }
    }
    already_computed = 1;
  }

  /* Lookup byte1+2, byte2+3, byte3+4 */
  parallel_for(out_idx = 0, in_idx = 0; in_idx < len; in_idx += 4,
out_idx += 3) {
    out[out_idx] = first[ in[in_idx] ][ in[in_idx+1] ];
    out[out_idx+1] = middle[ in[in_idx+1] ][ in[in_idx+2] ];
    out[out_idx+2] = last[ in[in_idx+2] ][ in[in_idx+3] ];
  }
}

== Improvement ideas ==

Use SIMD to do multiple 4-byte blocks in parallel - maybe a line at a
time?

Message sent:

Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-Mailer: MIME-tools 5.428 (Entity 5.428)
Content-Type: text/plain; charset=utf-8
X-Loop: help-debbugs@HIDDEN
From: help-debbugs@HIDDEN (GNU bug Tracking System)
To: Ole Tange <ole@HIDDEN>
Subject: bug#14158: Acknowledgement (Base64 -d is slow)
Message-ID: <handler.14158.B.136540669825210.ack <at> debbugs.gnu.org>
References: <CA+4vN7woWZBJ7aKHnxBADP=WjmMRJMn21sO1msadBwO+M3kWYg@HIDDEN>
X-Gnu-PR-Message: ack 14158
X-Gnu-PR-Package: coreutils
Reply-To: 14158 <at> debbugs.gnu.org
Date: Mon, 08 Apr 2013 07:39:02 +0000

Thank you for filing a new bug report with debbugs.gnu.org.

This is an automatically generated reply to let you know your message
has been received.

Your message is being forwarded to the package maintainers and other
interested parties for their attention; they will reply in due course.

Your message has been sent to the package maintainer(s):
 bug-coreutils@HIDDEN

If you wish to submit further information on this problem, please
send it to 14158 <at> debbugs.gnu.org.

Please do not send mail to help-debbugs@HIDDEN unless you wish
to report a problem with the Bug-tracking system.

--=20
14158: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D14158
GNU Bug Tracking System
Contact help-debbugs@HIDDEN with problems

Message sent to bug-coreutils@HIDDEN:

Subject: bug#14158: tag and classify
References: <CA+4vN7woWZBJ7aKHnxBADP=WjmMRJMn21sO1msadBwO+M3kWYg@HIDDEN>
In-Reply-To: <CA+4vN7woWZBJ7aKHnxBADP=WjmMRJMn21sO1msadBwO+M3kWYg@HIDDEN>
Resent-From: Bob Proulx <bob@HIDDEN>
Original-Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Resent-CC: bug-coreutils@HIDDEN
Resent-Date: Mon, 08 Apr 2013 20:02:02 +0000
Resent-Message-ID: <handler.14158.B14158.13654513083953 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: 14158 <at> debbugs.gnu.org
Date: Mon, 8 Apr 2013 13:58:08 -0600
From: Bob Proulx <bob@HIDDEN>
Message-ID: <20130408195808.GA31673@HIDDEN>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.5.21 (2010-09-15)
Precedence: list
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org

severity 14158 wishlist
tag 14158 + confirmed
thanks

Message received at control <at> debbugs.gnu.org:

Received: (at control) by debbugs.gnu.org; 8 Apr 2013 22:00:09 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Mon Apr 08 18:00:09 2013
Received: from localhost ([127.0.0.1]:40651 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1UPK6i-0003pm-NK
	for submit <at> debbugs.gnu.org; Mon, 08 Apr 2013 18:00:09 -0400
Received: from joseki.proulx.com ([216.17.153.58]:34693)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <bob@HIDDEN>) id 1UPK6g-0003pZ-AO
	for control <at> debbugs.gnu.org; Mon, 08 Apr 2013 18:00:07 -0400
Received: from hysteria.proulx.com (hysteria.proulx.com [192.168.230.119])
	by joseki.proulx.com (Postfix) with ESMTP id B8642211DF
	for <control <at> debbugs.gnu.org>; Mon,  8 Apr 2013 15:56:28 -0600 (MDT)
Received: by hysteria.proulx.com (Postfix, from userid 1000)
	id E9DF62DC8E; Mon,  8 Apr 2013 15:56:26 -0600 (MDT)
Date: Mon, 8 Apr 2013 15:56:26 -0600
From: Bob Proulx <bob@HIDDEN>
To: control <at> debbugs.gnu.org
Subject: tag and classify
Message-ID: <20130408215626.GA23159@HIDDEN>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Spam-Score: -1.6 (-)
X-Debbugs-Envelope-To: control
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: -2.4 (--)

severity 14158 wishlist
tag 14158 + confirmed
thanks

Message received at control <at> debbugs.gnu.org:

Received: (at control) by debbugs.gnu.org; 8 Apr 2013 22:00:09 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Mon Apr 08 18:00:09 2013
Received: from localhost ([127.0.0.1]:40651 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1UPK6i-0003pm-NK
	for submit <at> debbugs.gnu.org; Mon, 08 Apr 2013 18:00:09 -0400
Received: from joseki.proulx.com ([216.17.153.58]:34693)
	by debbugs.gnu.org with esmtp (Exim 4.72)
	(envelope-from <bob@HIDDEN>) id 1UPK6g-0003pZ-AO
	for control <at> debbugs.gnu.org; Mon, 08 Apr 2013 18:00:07 -0400
Received: from hysteria.proulx.com (hysteria.proulx.com [192.168.230.119])
	by joseki.proulx.com (Postfix) with ESMTP id B8642211DF
	for <control <at> debbugs.gnu.org>; Mon,  8 Apr 2013 15:56:28 -0600 (MDT)
Received: by hysteria.proulx.com (Postfix, from userid 1000)
	id E9DF62DC8E; Mon,  8 Apr 2013 15:56:26 -0600 (MDT)
Date: Mon, 8 Apr 2013 15:56:26 -0600
From: Bob Proulx <bob@HIDDEN>
To: control <at> debbugs.gnu.org
Subject: tag and classify
Message-ID: <20130408215626.GA23159@HIDDEN>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Spam-Score: -1.6 (-)
X-Debbugs-Envelope-To: control
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.13
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <http://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <http://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <http://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
	<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Sender: debbugs-submit-bounces <at> debbugs.gnu.org
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
X-Spam-Score: -2.4 (--)

severity 14158 wishlist
tag 14158 + confirmed
thanks

Message received at control <at> debbugs.gnu.org:

Received: (at control) by debbugs.gnu.org; 19 Oct 2018 01:46:53 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Thu Oct 18 21:46:53 2018
Received: from localhost ([127.0.0.1]:57955 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1gDJsL-0004j0-4h
	for submit <at> debbugs.gnu.org; Thu, 18 Oct 2018 21:46:53 -0400
Received: from mail-it1-f176.google.com ([209.85.166.176]:51210)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <assafgordon@HIDDEN>) id 1gDJsH-0004d4-8v
 for control <at> debbugs.gnu.org; Thu, 18 Oct 2018 21:46:51 -0400
Received: by mail-it1-f176.google.com with SMTP id 74-v6so2697038itw.1
 for <control <at> debbugs.gnu.org>; Thu, 18 Oct 2018 18:46:49 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=to:from:message-id:date:user-agent:mime-version:content-language
 :content-transfer-encoding;
 bh=ZdUllPO9rceYmfqg6TimccbBGVaWBDNphLPEypnl4vk=;
 b=h6ma4dEBFaN9/W2Ovuy3MyT8YRr1zScUiTYgwzwdJl2KVmJmZQ6/7URDcw6aIabdpy
 OWKuafguWIgnkvSeME73G0hQVkl0bFO+IJwgn75lv3bFcuyRyrM64XqrzlahxMFvGigb
 oFgrROF7j3fIghmSBfugNM0oEPCwbdNU5NhVv4V3y0lInXvCI9oYbrUD47B3rk/A6BQq
 TZqhGoi58C+/zXOLfAyF/Xw0aIdsJzUammKFM2zCnb9rLunbsy9DprmtRH48yuMZ59x/
 egrRS+SxMjscfXVPz91uM3+apdwbkhJacIorZd/iVB3lH6+VVjHGJul0ZgiNE3SA80CR
 /ZPw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:to:from:message-id:date:user-agent:mime-version
 :content-language:content-transfer-encoding;
 bh=ZdUllPO9rceYmfqg6TimccbBGVaWBDNphLPEypnl4vk=;
 b=TN3uMLssrl6mjHXc7l6AUrIqPrjaZUItWZlnnBVqwqmcesZKnwF5wKT/IJq3GVQkTt
 HC5LcIc4CSdOLHdql6fNdRLhIqwFrGc5YOU8gQCom91F3U3vUhHpQFBzjFRzVuge1h24
 rGTnxAXf0PgvuEjeK7PcRHCJVEik2gy/gwTU6VHTF1qGJoor0wPfBpRnKYaBLd0CvNUe
 pKKki+Op9WfhTXYamKF5Qw8zOG5rMafJh9rPZ2ftPTwsj7E4oJdT2giKi75CNlHVyLox
 qKbtfD4QWDXrlaoNebdSp2HO/EN2djdc8w2vUw+mdutJ+ikj4Ptntha1LUUrhmU0IZpD
 8LTA==
X-Gm-Message-State: ABuFfoi6u5Mc8qs3fVk9xAal0xY+RhSSMB79Gzl2i3Dz6N53XWJma4MT
 EMuqE52cs8ZkH/+qYnZhzXzcmsLEayw=
X-Google-Smtp-Source: ACcGV60HDKGkEXMDPk0erbWeQjuQhs6d6hhepkRF689/H4tRgSE+a5kKdZU8kGfvOqmsbmxomH2vLg==
X-Received: by 2002:a02:59d6:: with SMTP id
 v83-v6mr4159732jad.129.1539913603345; 
 Thu, 18 Oct 2018 18:46:43 -0700 (PDT)
Received: from tomato.housegordon.com (moose.housegordon.com. [184.68.105.38])
 by smtp.googlemail.com with ESMTPSA id
 w71-v6sm931395ita.0.2018.10.18.18.46.41 for <control <at> debbugs.gnu.org>
 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
 Thu, 18 Oct 2018 18:46:42 -0700 (PDT)
To: control <at> debbugs.gnu.org
From: Assaf Gordon <assafgordon@HIDDEN>
Message-ID: <6f6fb09c-3939-b3f6-6954-d2fbb7749abd@HIDDEN>
Date: Thu, 18 Oct 2018 19:46:41 -0600
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101
 Thunderbird/52.9.1
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 7bit
X-Spam-Score: 2.0 (++)
X-Spam-Report: Spam detection software, running on the system "debbugs.gnu.org",
 has NOT identified this incoming email as spam.  The original
 message has been attached to this so you can view it or label
 similar future email.  If you have any questions, see
 the administrator of that system for details.
 Content preview:  severity 5962 wishlist retitle 5962 performance: improving
 SHA1 using intel SS3 instructions retitle 14158 performance: Base64 -d is
 slow [...] 
 Content analysis details:   (2.0 points, 10.0 required)
 pts rule name              description
 ---- ---------------------- --------------------------------------------------
 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
 (assafgordon[at]gmail.com)
 -0.0 SPF_PASS               SPF: sender matches SPF record
 -0.0 RCVD_IN_MSPIKE_H2      RBL: Average reputation (+2)
 [209.85.166.176 listed in wl.mailspike.net]
 -0.0 RCVD_IN_DNSWL_NONE     RBL: Sender listed at http://www.dnswl.org/, no
 trust [209.85.166.176 listed in list.dnswl.org]
 1.8 MISSING_SUBJECT        Missing Subject: header
 0.2 NO_SUBJECT             Extra score for no subject
X-Debbugs-Envelope-To: control
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: 1.0 (+)

severity 5962 wishlist
retitle 5962 performance: improving SHA1 using intel SS3 instructions

retitle 14158 performance: Base64 -d is slow

Last modified: Mon, 25 Nov 2019 12:00:02 UTC

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997 nCipher Corporation Ltd, 1994-97 Ian Jackson.