Comments (15)
marklister
commented on July 21, 2024
Yes, it'd be interesting to microbenchmark this code vs the various alternatives.
from base64.
marklister
commented on July 21, 2024
I'd imagine that using BigInt is probably a fair old bottleneck as well.
from base64.
marklister
commented on July 21, 2024
Here's an idea:
scala> val decodeTable=encodeTable.zipWithIndex.toMap
decodeTable: scala.collection.immutable.Map[Char,Int] = Map(E -> 4, e -> 30, X -> 23, s -> 44, x -> 49, 8 -> 60, 4 -> 56, n -> 39, 9 -> 61, N -> 13, j -> 35, y -> 50, T -> 19, Y -> 24, t -> 45, J -> 9, u -> 46, U -> 20, f -> 31, F -> 5, A -> 0, a -> 26, 5 -> 57, m -> 38, M -> 12, I -> 8, i -> 34, v -> 47, G -> 6, 6 -> 58, 1 -> 53, V -> 21, q -> 42, Q -> 16, L -> 11, b -> 27, g -> 32, B -> 1, l -> 37, P -> 15, p -> 41, 0 -> 52, 2 -> 54, C -> 2, H -> 7, + -> 62, c -> 28, W -> 22, h -> 33, 7 -> 59, r -> 43, K -> 10, w -> 48, R -> 17, 3 -> 55, k -> 36, O -> 14, / -> 63, D -> 3, Z -> 25, o -> 40, z -> 51, S -> 18, d -> 29)
scala> decodeTable('a')
res0: Int = 26
scala> decodeTable('A')
res1: Int = 0
from base64.
baturinsky
commented on July 21, 2024
Array may be faster than map. But possibly less "idiomatical" :) And require extra step for converting char to char code.
from base64.
marklister
commented on July 21, 2024
An array is probably going to be doing 32 comparisons on average isn't it? Whereas the default Map implementation is a Hash Trie (HashMap) and there's also the option of a red black tree (TreeMap). The Map will add only one line to the source.
from base64.
marklister
commented on July 21, 2024
The Red Black Tree is probably the better choice:
scala> val decodeTable=collection.immutable.TreeMap(encodeTable.zipWithIndex : _*)
decodeTable: scala.collection.immutable.TreeMap[Char,Int] = Map(+ -> 62, / -> 63, 0 -> 52, 1 -> 53, 2 -> 54, 3 -> 55, 4 -> 56, 5 -> 57, 6 -> 58, 7 -> 59, 8 -> 60, 9 -> 61, A -> 0, B -> 1, C -> 2, D -> 3, E -> 4, F -> 5, G -> 6, H -> 7, I -> 8, J -> 9, K -> 10, L -> 11, M -> 12, N -> 13, O -> 14, P -> 15, Q -> 16, R -> 17, S -> 18, T -> 19, U -> 20, V -> 21, W -> 22, X -> 23, Y -> 24, Z -> 25, a -> 26, b -> 27, c -> 28, d -> 29, e -> 30, f -> 31, g -> 32, h -> 33, i -> 34, j -> 35, k -> 36, l -> 37, m -> 38, n -> 39, o -> 40, p -> 41, q -> 42, r -> 43, s -> 44, t -> 45, u -> 46, v -> 47, w -> 48, x -> 49, y -> 50, z -> 51)
Basically we're looking for an efficient function (Char)=>Int. I'm not sure how to do that with an Array?
from base64.
baturinsky
commented on July 21, 2024
Use Character.getNumericValue(char) to get char's numeric value and lookup 128-length array
from base64.
marklister
commented on July 21, 2024
For now I'm going to do this with a TreeMap. If we can prove that an array done as you suggest is significantly more efficient I'll switch to that but for now I don't think it warrants the ugliness...
from base64.
marklister
commented on July 21, 2024
from base64.
marklister
commented on July 21, 2024
It's not as ugly as I thought it would be:
scala> val decodeTable=new Array[Int](128)
decodeTable: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
scala> encodeTable.zipWithIndex.foreach(x=>decodeTable(x._1.toInt)=x._2)
scala> decodeTable
res5: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 62, 0, 0, 0, 63, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 0, 0, 0, 0, 0, 0, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 0, 0, 0, 0, 0)
scala> decodeTable('a'.toInt)
res6: Int = 26
Maybe some benchmarking might be in order?
from base64.
baturinsky
commented on July 21, 2024
Scala is good at making complex things simple:) In most other languages elliptic curve crypto libs looks way more messy.
Benchmarking would be good. But I'm not familiar with how it's done in Scala.
from base64.
marklister
commented on July 21, 2024
The first one is using a Treemap the second an array the third a HashMap. The major performance problem is with encoding not decoding.
Microbenchmark
===============
..........Encode microbenchmank:
Encode size:118550 bytes
Encode time:16494 ms
..........Decode microbenchmark
Decode size:158080 chars
Decode time:3177 ms
[success] Total time: 25 s, completed Oct 8, 2014 12:48:46 AM
> run
[info] Compiling 1 Scala source to /home/mark/scalaProjects/base64/target/scala-2.10/classes...
[info] Compiling 1 Scala source to /home/mark/scalaProjects/base64/target/scala-2.10/classes...
[info] Running Benchmark
Microbenchmark
===============
..........Encode microbenchmank:
Encode size:118550 bytes
Encode time:16438 ms
..........Decode microbenchmark
Decode size:158080 chars
Decode time:3248 ms
Microbenchmark
===============
..........Encode microbenchmank:
Encode size:118550 bytes
Encode time:16475 ms
..........Decode microbenchmark
Decode size:158080 chars
Decode time:3264 ms
from base64.
marklister
commented on July 21, 2024
I put together some basic benchmarking. It seems there almost no difference between using an Array or a Treemap for lookup. BigInt however is a big killjoy when it comes to performance.
Having eliminated BigInt i'm seeing good performance:
Microbenchmark
===============
..........Encode microbenchmank:
Encode size:118550 bytes
Encode time:185 ms
..........Decode microbenchmark
Decode size:158080 chars
Decode time:208 ms
from base64.
baturinsky
commented on July 21, 2024
So, BigInt was the bottleneck. It could be worth testing different decoding methods after removing it - tens of milliseconds difference can be noticeable now.
from base64.
marklister
commented on July 21, 2024
I've benchmarked it already after removing BigInt. Basically zero difference between HashMap, TreeMap and Array. TreeMap looked like it might have a slight edge. My benchmark is not professional but it looks like it does the job.
from base64.
Related Issues (13)
- def enc not tail recursive. HOT 1
- String concat not preferred HOT 1
- base64url HOT 8
- Encoding is not compatible with Browser decoding HOT 6
- Strict padding unnecessary -- causes JS interop problem HOT 19
- Document using base64Url better
- Consider structures other than `Array[Byte]` HOT 11
- Improve performance HOT 1
- Publish the latest version HOT 4
- Using '=' for padding does not work for URLs HOT 7
- 0.2.5 jars are empty on maven central HOT 4
- Release with latest scalajs 1.x? HOT 4
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from base64.