Does Redis really need exact string representation of decimal value from double
727 views
Skip to first unread message
Mikhail Mikheev
Oct 28, 2011, 3:50:33 AM10/28/11
to Redis DB
I uses ServiceStack.Redis client to access Redis and found that if I
use commands like ZADD, ZRANGEBYSCORE etc. which have double
parameters with quite big values then a cpecial code is used to
convert double to exact string representation of decimal value (who is
familiar with ServiceStack i'm talking about DoubleConverter class).
And under reasonable load this code performs unefficiently increasing
pressure on memory.
I have some ideas how to decrease memory consumtion. But befor I start
with this i'd like to ask is it really needed to get exact string
representation of decimal value from double to send to Redis.
Can't we just use ToString("r") on double in .Net to get round-trip
representation of double value? At least ToStrign("r") guarantees
that .Net will parse resulting string to the same double. But the real
question is how does Redis parse string representation of double?
I use Redis compiled on Windows with MinGW but im interesting if
there will be any differences between parsing the string returned by
ToString("r") in .Net and Redis compiled on MinGW and *nix platforms?
PS. I wanted to post this question to ServiceStack dedicated group
first but finally have decided that the question is general and can be
applied to any client rather than to ServiceStack only. So here is
other question how do other clients convert double to bytes before
sending to Redis?
use commands like ZADD, ZRANGEBYSCORE etc. which have double
parameters with quite big values then a cpecial code is used to
convert double to exact string representation of decimal value (who is
familiar with ServiceStack i'm talking about DoubleConverter class).
And under reasonable load this code performs unefficiently increasing
pressure on memory.
I have some ideas how to decrease memory consumtion. But befor I start
with this i'd like to ask is it really needed to get exact string
representation of decimal value from double to send to Redis.
Can't we just use ToString("r") on double in .Net to get round-trip
representation of double value? At least ToStrign("r") guarantees
that .Net will parse resulting string to the same double. But the real
question is how does Redis parse string representation of double?
I use Redis compiled on Windows with MinGW but im interesting if
there will be any differences between parsing the string returned by
ToString("r") in .Net and Redis compiled on MinGW and *nix platforms?
PS. I wanted to post this question to ServiceStack dedicated group
first but finally have decided that the question is general and can be
applied to any client rather than to ServiceStack only. So here is
other question how do other clients convert double to bytes before
sending to Redis?
Demis Bellot
Oct 28, 2011, 9:53:47 AM10/28/11
to redi...@googlegroups.com
Actually you're right, I just created a quick set of benchmarks here:
--
- Demis
With results for 100,000 iterations:
double.ToString(): Completed in ms: 41
double.ToString('r') completed in ms: 65
DoubleConverter.ToExactString(): Completed in ms: 1733
BitConverter.ToString() completed in ms: 46
double.ToString('G') completed in ms: 40
So yeah the current method is quite a bit slower. I'm actually surprised just how slow it is myself.
While I don't remember the exact reason why I went down the DoubleConverter route, I do believe that I may have been burnt by inaccurate values of doube.ToString().
I'll try switching it over tonight and run a few tests to make sure nothing breaks.
Thanks for picking this up!
Cheers,
--
You received this message because you are subscribed to the Google Groups "Redis DB" group.
To post to this group, send email to redi...@googlegroups.com.
To unsubscribe from this group, send email to redis-db+u...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/redis-db?hl=en.
- Demis
Mikhail Mikheev
Oct 31, 2011, 10:52:25 AM10/31/11
to Redis DB
Demis,
Here is the code below how I changed ArbitraryDecimal class (under
DoubleConverter) to reduce memory consumption. I'm not familiar with
Git so can't push it upstream. The idea is simple I use two arrays
with capacity allocated in advance (2 times more than current mantissa
length) and swap them time to time instead of creating a new arrays.
My use case was doubles arrount E+17 (which is actually DateTime.Ticks
value as I use zsets to store values sorted by dates):
One more idea I implement is that double is not really needed all the
times so in most cases integer value is enough for score. As the
result by adding overloads that accepts longs with for those methods
that accept doubles may solve this problem without addressing double
to exact decimal representation problem at all, because if you convert
long to string it will be parsed well on Redis side (but of course it
is not guaranteed that the score in Redis will be the same number as
you sent as it due to double rounding on Redis side)
/// <summary>Private class used for manipulating
class ArbitraryDecimal
{
/// <summary>Digits in the decimal expansion, one byte per digit</
summary>
MyArraySegment digits;
/// <summary>Reference to array segments that currently acts as a
buffer</summary>
MyArraySegment buffer;
/// <summary>
/// How many digits are *after* the decimal point
/// </summary>
int decimalPoint;
/// <summary>
/// Constructs an arbitrary decimal expansion from the given long.
/// The long must not be negative.
/// </summary>
internal ArbitraryDecimal(long x)
{
string tmp = x.ToString(CultureInfo.InvariantCulture);
digits = new MyArraySegment(new byte[tmp.Length * 2], 0,
tmp.Length - 1);
for (int i = 0; i < tmp.Length; i++)
digits[i] = (byte)(tmp[i] - '0');
buffer = new MyArraySegment(new byte[tmp.Length * 2]);
Normalize();
}
/// <summary>
/// Multiplies the current expansion by the given amount, which
should
/// only be 2 or 5.
/// </summary>
internal void MultiplyBy(int amount)
{
if (buffer.SetWindow(0, digits.Length))
buffer[digits.Length] = 0; // we flush only last digit as only it
will take part in the calculation
else
buffer = new MyArraySegment(new byte[digits.Length + 1], 0,
digits.Length);
for (int i = digits.Length - 1; i >= 0; i--)
{
int resultDigit = digits[i] * amount + buffer[i + 1];
buffer[i] = (byte)(resultDigit / 10);
buffer[i + 1] = (byte)(resultDigit % 10);
}
if (buffer[0] != 0)
{
SwapBufferAndDigits();
}
else
{
buffer.SqueezeFromLeft(1);
SwapBufferAndDigits();
}
Normalize();
}
/// <summary>
/// Shifts the decimal point; a negative value makes
/// the decimal expansion bigger (as fewer digits come after the
/// decimal place) and a positive value makes the decimal
/// expansion smaller.
/// </summary>
internal void Shift(int amount)
{
decimalPoint += amount;
}
/// <summary>
/// Removes leading/trailing zeroes from the expansion.
/// </summary>
internal void Normalize()
{
int first;
for (first = 0; first < digits.Length; first++)
if (digits[first] != 0)
break;
int last;
for (last = digits.Length - 1; last >= 0; last--)
if (digits[last] != 0)
break;
if (first == 0 && last == digits.Length - 1)
return;
int rightIndex = last - first;
if (!buffer.SetWindow(0, rightIndex))
buffer = new MyArraySegment(new byte[rightIndex + 1], 0,
rightIndex);
for (int i = 0; i < buffer.Length; i++)
buffer[i] = digits[i + first];
decimalPoint -= digits.Length - (last + 1);
SwapBufferAndDigits();
}
/// <summary>
/// Converts the value to a proper decimal string representation.
/// </summary>
public override String ToString()
{
char[] digitString = new char[digits.Length];
for (int i = 0; i < digits.Length; i++)
digitString[i] = (char)(digits[i] + '0');
// Simplest case - nothing after the decimal point,
// and last real digit is non-zero, eg value=35
if (decimalPoint == 0)
{
return new string(digitString);
}
// Fairly simple case - nothing after the decimal
// point, but some 0s to add, eg value=350
if (decimalPoint < 0)
{
return new string(digitString) +
new string('0', -decimalPoint);
}
// Nothing before the decimal point, eg 0.035
if (decimalPoint >= digitString.Length)
{
return "0." +
new string('0', (decimalPoint - digitString.Length)) +
new string(digitString);
}
// Most complicated case - part of the string comes
// before the decimal point, part comes after it,
// eg 3.5
return new string(digitString, 0,
digitString.Length - decimalPoint) +
"." +
new string(digitString,
digitString.Length - decimalPoint,
decimalPoint);
}
private void SwapBufferAndDigits()
{
MyArraySegment tmp = digits;
digits = buffer;
buffer = tmp;
}
}
private class MyArraySegment
{
private readonly byte[] _array;
private int _left;
private int _right;
public MyArraySegment(byte[] array, int left = 0, int right = 0)
{
_array = array;
_left = left;
_right = right;
}
public byte this[int index]
{
get { return _array[_left + index]; }
set { _array[_left + index] = value; }
}
public int Length
{
get { return _right - _left + 1; }
}
public void SqueezeFromLeft(int delta)
{
_left += delta;
}
public bool SetWindow(int left, int right)
{
if (left >= 0 && right < _array.Length)
{
_left = left;
_right = right;
return true;
}
return false;
}
}
On 28 окт, 17:53, Demis Bellot <demis.bel...@gmail.com> wrote:
> Actually you're right, I just created a quick set of benchmarks here:https://github.com/ServiceStack/ServiceStack.Redis/blob/master/tests/...
Here is the code below how I changed ArbitraryDecimal class (under
DoubleConverter) to reduce memory consumption. I'm not familiar with
Git so can't push it upstream. The idea is simple I use two arrays
with capacity allocated in advance (2 times more than current mantissa
length) and swap them time to time instead of creating a new arrays.
My use case was doubles arrount E+17 (which is actually DateTime.Ticks
value as I use zsets to store values sorted by dates):
One more idea I implement is that double is not really needed all the
times so in most cases integer value is enough for score. As the
result by adding overloads that accepts longs with for those methods
that accept doubles may solve this problem without addressing double
to exact decimal representation problem at all, because if you convert
long to string it will be parsed well on Redis side (but of course it
is not guaranteed that the score in Redis will be the same number as
you sent as it due to double rounding on Redis side)
/// <summary>Private class used for manipulating
class ArbitraryDecimal
{
/// <summary>Digits in the decimal expansion, one byte per digit</
summary>
MyArraySegment digits;
/// <summary>Reference to array segments that currently acts as a
buffer</summary>
MyArraySegment buffer;
/// <summary>
/// How many digits are *after* the decimal point
/// </summary>
int decimalPoint;
/// <summary>
/// Constructs an arbitrary decimal expansion from the given long.
/// The long must not be negative.
/// </summary>
internal ArbitraryDecimal(long x)
{
string tmp = x.ToString(CultureInfo.InvariantCulture);
digits = new MyArraySegment(new byte[tmp.Length * 2], 0,
tmp.Length - 1);
for (int i = 0; i < tmp.Length; i++)
digits[i] = (byte)(tmp[i] - '0');
buffer = new MyArraySegment(new byte[tmp.Length * 2]);
Normalize();
}
/// <summary>
/// Multiplies the current expansion by the given amount, which
should
/// only be 2 or 5.
/// </summary>
internal void MultiplyBy(int amount)
{
if (buffer.SetWindow(0, digits.Length))
buffer[digits.Length] = 0; // we flush only last digit as only it
will take part in the calculation
else
buffer = new MyArraySegment(new byte[digits.Length + 1], 0,
digits.Length);
for (int i = digits.Length - 1; i >= 0; i--)
{
int resultDigit = digits[i] * amount + buffer[i + 1];
buffer[i] = (byte)(resultDigit / 10);
buffer[i + 1] = (byte)(resultDigit % 10);
}
if (buffer[0] != 0)
{
SwapBufferAndDigits();
}
else
{
buffer.SqueezeFromLeft(1);
SwapBufferAndDigits();
}
Normalize();
}
/// <summary>
/// Shifts the decimal point; a negative value makes
/// the decimal expansion bigger (as fewer digits come after the
/// decimal place) and a positive value makes the decimal
/// expansion smaller.
/// </summary>
internal void Shift(int amount)
{
decimalPoint += amount;
}
/// <summary>
/// Removes leading/trailing zeroes from the expansion.
/// </summary>
internal void Normalize()
{
int first;
for (first = 0; first < digits.Length; first++)
if (digits[first] != 0)
break;
int last;
for (last = digits.Length - 1; last >= 0; last--)
if (digits[last] != 0)
break;
if (first == 0 && last == digits.Length - 1)
return;
int rightIndex = last - first;
if (!buffer.SetWindow(0, rightIndex))
buffer = new MyArraySegment(new byte[rightIndex + 1], 0,
rightIndex);
for (int i = 0; i < buffer.Length; i++)
buffer[i] = digits[i + first];
decimalPoint -= digits.Length - (last + 1);
SwapBufferAndDigits();
}
/// <summary>
/// Converts the value to a proper decimal string representation.
/// </summary>
public override String ToString()
{
char[] digitString = new char[digits.Length];
for (int i = 0; i < digits.Length; i++)
digitString[i] = (char)(digits[i] + '0');
// Simplest case - nothing after the decimal point,
// and last real digit is non-zero, eg value=35
if (decimalPoint == 0)
{
return new string(digitString);
}
// Fairly simple case - nothing after the decimal
// point, but some 0s to add, eg value=350
if (decimalPoint < 0)
{
return new string(digitString) +
new string('0', -decimalPoint);
}
// Nothing before the decimal point, eg 0.035
if (decimalPoint >= digitString.Length)
{
return "0." +
new string('0', (decimalPoint - digitString.Length)) +
new string(digitString);
}
// Most complicated case - part of the string comes
// before the decimal point, part comes after it,
// eg 3.5
return new string(digitString, 0,
digitString.Length - decimalPoint) +
"." +
new string(digitString,
digitString.Length - decimalPoint,
decimalPoint);
}
private void SwapBufferAndDigits()
{
MyArraySegment tmp = digits;
digits = buffer;
buffer = tmp;
}
}
private class MyArraySegment
{
private readonly byte[] _array;
private int _left;
private int _right;
public MyArraySegment(byte[] array, int left = 0, int right = 0)
{
_array = array;
_left = left;
_right = right;
}
public byte this[int index]
{
get { return _array[_left + index]; }
set { _array[_left + index] = value; }
}
public int Length
{
get { return _right - _left + 1; }
}
public void SqueezeFromLeft(int delta)
{
_left += delta;
}
public bool SetWindow(int left, int right)
{
if (left >= 0 && right < _array.Length)
{
_left = left;
_right = right;
return true;
}
return false;
}
}
On 28 окт, 17:53, Demis Bellot <demis.bel...@gmail.com> wrote:
> Actually you're right, I just created a quick set of benchmarks here:https://github.com/ServiceStack/ServiceStack.Redis/blob/master/tests/...
>
> With results for 100,000 iterations:
>
> double.ToString(): Completed in ms: 41
>
> > double.ToString('r') completed in ms: 65
> > DoubleConverter.ToExactString(): Completed in ms: 1733
> > BitConverter.ToString() completed in ms: 46
> > double.ToString('G') completed in ms: 40
>
> So yeah the current method is quite a bit slower. I'm actually surprised
> just how slow it is myself.
> While I don't remember the exact reason why I went down the DoubleConverter
> route, I do believe that I may have been burnt by inaccurate values of
> doube.ToString().
>
> I'll try switching it over tonight and run a few tests to make sure nothing
> breaks.
>
> Thanks for picking this up!
>
> Cheers,
>
> With results for 100,000 iterations:
>
> double.ToString(): Completed in ms: 41
>
> > double.ToString('r') completed in ms: 65
> > DoubleConverter.ToExactString(): Completed in ms: 1733
> > BitConverter.ToString() completed in ms: 46
> > double.ToString('G') completed in ms: 40
>
> So yeah the current method is quite a bit slower. I'm actually surprised
> just how slow it is myself.
> While I don't remember the exact reason why I went down the DoubleConverter
> route, I do believe that I may have been burnt by inaccurate values of
> doube.ToString().
>
> I'll try switching it over tonight and run a few tests to make sure nothing
> breaks.
>
> Thanks for picking this up!
>
> Cheers,
>
Demis Bellot
Oct 31, 2011, 11:56:01 AM10/31/11
to redi...@googlegroups.com
Hi Mikhail,
Thx for this class although just this weekend I've already pushed a version of the Redis client (v2.28) that just uses
double.ToString("G", CultureInfo.InvariantCulture); since it's comparatively quick and is the same method that Booksleve uses (the other popular Redis Client).
As expected that does result in a tiny loss of fraction. I'll have a look at this class and check to see if it's a better fit.
BTW how does your Arbitrary decimal class convert to/from a double?
I also agree that it makes sense to have a int/long score, so I'll look at adding these overloads as well.
Thanks,
Demis
Demis Bellot
Nov 1, 2011, 12:39:18 AM11/1/11
to redi...@googlegroups.com
Hi Mikhail,
The latest version of the Redis client now has 'long' score overloads for Sorted Set operations that had previously only had double scores:
Latest version is on NuGet or can be downloaded from:
Cheers,
Mikhail Mikheev
Nov 1, 2011, 2:55:53 AM11/1/11
to Redis DB
Demis,
Speaking about your question:
> > BTW how does your Arbitrary decimal class convert to/from a double?
I'm not sure about what you meant. But it is not a new class. It
existed before (DoubleConverter used it to store decimal
representation of double) I've just refactored it a bit to reduce
byte[] arrays allocation. It was used to conver big ot very small
doubles to string but not vice versa. Even after my refactoring I'm
sure it is slow enough so I would prefer ToString("r"). However
ToString("g") should be also enough in most cases.
I hope that ToString("g") will be enough for most cases so we may
forgot about DoubleConverter. At least let's check if someone report
any issues related to this topic on a new version the Redis client.
If any of the authors of other Redis clients (including ones written
for languages other than .Net) are here I just wonder how do you
conver doubles to bytes before sending to Redis? Did you face any
issue with parsing doubles to different values on Redis side?
On 1 ноя, 08:39, Demis Bellot <demis.bel...@gmail.com> wrote:
> Hi Mikhail,
>
> The latest version of the Redis client now has 'long' score overloads for
> Sorted Set operations that had previously only had double scores:
> Latest version is on NuGet or can be downloaded from:https://github.com/ServiceStack/ServiceStack.Redis/downloads
>
> Cheers,
>
> On Mon, Oct 31, 2011 at 11:56 AM, Demis Bellot <demis.bel...@gmail.com>wrote:
>
>
>
>
>
>
>
> > Hi Mikhail,
> > Thx for this class although just this weekend I've already pushed a
> > version of the Redis client (v2.28) that just uses
> > double.ToString("G", CultureInfo.InvariantCulture); since it's
> > comparatively quick and is the same method that Booksleve uses (the other
> > popular Redis Client).
>
> > As expected that does result in a tiny loss of fraction. I'll have a look
> > at this class and check to see if it's a better fit.
> > BTW how does your Arbitrary decimal class convert to/from a double?
>
> > I also agree that it makes sense to have a int/long score, so I'll look at
> > adding these overloads as well.
>
> > Thanks,
> > Demis
>
> > On Mon, Oct 31, 2011 at 10:52 AM, Mikhail Mikheev <michail_mikh...@mail.ru
> ...
>
> продолжение »
Demis Bellot
Nov 1, 2011, 3:06:53 AM11/1/11
to redi...@googlegroups.com
Hi Mikhail,
Well I ultimately ended up going with:
value.ToString("G", CultureInfo.InvariantCulture);
Because that's what BookSleeve client was using:
There's a tiny loss of precision (i.e. I have a failing test) but its not by much:
Expected: 1.2345678901234567E+19d
But was: 1.23456789012346E+19d
Note: I've added overloads for long scores on the IRedisNativeClient/IRedisClient APIs in the latest release:
--
You received this message because you are subscribed to the Google Groups "Redis DB" group.
To post to this group, send email to redi...@googlegroups.com.
To unsubscribe from this group, send email to redis-db+u...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/redis-db?hl=en.
Marc Gravell
Nov 1, 2011, 8:08:49 AM11/1/11
to redi...@googlegroups.com
Which all begs the question for Salvatore: since there is a binary-safe API, can we please just optionally throw IEEE-754 encoded data over the wire ;p
(said in complete ignorance of the possible side-effects of such)
--
Regards,
Marc
(said in complete ignorance of the possible side-effects of such)
Marc
2011/11/1 Demis Bellot <demis....@gmail.com>
Regards,
Marc
Reply all
Reply to author
Forward
0 new messages