Double Parser

[zorfmorf]

Hi everyone,

I'm currently working on a small online game, mainly to become familiar with networking in lua (the server is written in java, the client in löve).

Everything works so far, aside from the game freezing for a very short time every few seconds on my (very slow) netbook. It's not really bad, but quite annoying. I have figured out, that the problem lies in my double parser (that obviously parses doubles from the recieved datagrams). The server sends out a datagram every 0.1 second and every datagram has six double values that need to be parsed. However, every few seconds, lua takes over 0.05 seconds to parse the package and exactly at that moment the game freezes very shortly.

I was wondering if anyone is able to give me some tips on how to optimize my parser or willing to share his implementation:

A datagram package contains doubles as defined in http://en.wikipedia.org/wiki/IEEE_754-2008

Code: Select all

-- dataStream is the string containing the double, startIndex defines, where the double starts
function parseDouble(dataStream, startIndex)
    return (-1)^(getSign(dataStream, startIndex)) * 2^(getExponent(dataStream, startIndex) - 1023) * (1 + getMantisse(dataStream, startIndex) / 2^(52))
end

function getMantisse(dataStream, startIndex)
	tempDouble = (string.byte(dataStream, startIndex + 1) % 16) * 256^6
	for i=2,7 do
        tempDouble = tempDouble + string.byte(dataStream, startIndex + i) * 256^(7-i)
    end
    return tempDouble
end

function getExponent(dataStream, startIndex)
	local exponent = string.byte(dataStream, startIndex + 1) - (string.byte(dataStream, startIndex + 1) % 16)
    exponent = exponent / 16 + (string.byte(dataStream, startIndex) % 128) * 16
    return exponent
end

function getSign(dataStream, startIndex)
	if string.byte(dataStream, startIndex) > 127 then
		return 1
	else
		return 0
	end
end

[miko]

I was wondering if anyone is able to give me some tips on how to optimize my parser or willing to share his implementation:

I have 2 tips:
1. use simpler format for data, lo Love could parse it directly ( I am assuming the server is more powerful, so could handle the overhead of converting the data for love client)
2. use love compiled with luajit, and use its binary library to get some speed up

[tentus]

Code: Select all

function getMantisse(dataStream, startIndex)
	local tempDouble = (string.byte(dataStream, startIndex + 1) % 16) * 256^6
	for i=2,7 do
		tempDouble = tempDouble + string.byte(dataStream, startIndex + i) * 256^(7-i)
	end
	return tempDouble
end

You could get a small (very small) performance increase by making tempDouble a local, like above. The following change doesn't help performance but it does reduce the number of lines:

Code: Select all

function getSign(dataStream, startIndex)
	if string.byte(dataStream, startIndex) > 127 then
		return 1
	end
	return 0
end

Other than that I can't really help you out. Try and think of a way to avoid modulo, it's slow comparatively speaking. Also, benchmark different variations: sometimes you can get speed increases from odd places, places that wouldn't occur to you as a human being.

[zorfmorf]

I have 2 tips:
1. use simpler format for data, lo Love could parse it directly ( I am assuming the server is more powerful, so could handle the overhead of converting the data for love client)
2. use love compiled with luajit, and use its binary library to get some speed up

Thanks for the tip! I didn't know about luajit, seems very usefull. Trying it out just now.

You could get a small (very small) performance increase by making tempDouble a local, like above.
Other than that I can't really help you out. Try and think of a way to avoid modulo, it's slow comparatively speaking. Also, benchmark different variations: sometimes you can get speed increases from odd places, places that wouldn't occur to you as a human being.

Awww, I really liked modulo until you told me about its slow performance...

Well, thank you two! I will try your tips out and see if it helps me in any way. Additionally, I'm currently trying to move my udp handler into it's own thread. We'll see how that goes. If that doesn't work, I will have to face the fact that I need to send the the state as a string, considering that I bumb into performance issues with just one object. The server performance itself is not the issue, I'm more bugged by the prospect, that it will half the amount of information I can cram into one datagram.

[Boolsheet]

I doubt it's your double parser. The function only takes 3 microseconds for one call on my system.
Could there be something else slowing it down?

Here's my implementation:

Code: Select all

local strbyte = string.byte
local POWN1022 = 2^-1022
local INFINITY = math.huge

function double_to_number(double, big_endian)
	local f8, f7, f6, f5, f4, f3, f2, f1 = strbyte(double, 1, 8)

	if big_endian then
		f1, f2, f3, f4, f5, f6, f7, f8 = f8, f7, f6, f5, f4, f3, f2, f1
	end

	local sgn = 1
	local exp = f1*16
	if f1 >= 128 then
		sgn = -1
		exp = exp - 2048
	end

	local msm = f2%16
	exp = exp + (f2 - msm)*0.0625
	local man = msm*281474976710656 + f3*1099511627776 + f4*4294967296 + f5*16777216 + f6*65536 + f7*256 + f8

	if exp == 0 then
		return sgn * (man*(1/4503599627370496)) * POWN1022
	elseif exp == 2047 then
		if man == 0 then
			return sgn * INFINITY
		else
			return 0/0
		end
	else
		return sgn * (1 + man*(1/4503599627370496)) * 2^(exp-1023)
	end
end

[zorfmorf]

Thanks for sharing your parser, it helped me improve mine a bit.

After some more testing, I came to the conclusion that running löve, a java server, firefox, eclipse and geany at the same time may just be a little bit too much for my netbook to handle...

In retrospect I don't know why it took me so long to see this