This change is the result of a conversation on IRC.
The current decoder spec used by coro-net, coro-channel, http-codec, websocket-codec, etc causes a lot of unnecessary copies of network data.
In particular there are some problem areas with the decoder interface which requires the input chunk to start at index 1 and requires returning the full extra buffer as a new string.
If a message spans many chunks, then the data is concatenated repeatedly until enough data is buffered. This has a cost of O(m * n) where m is total message length and n is number of chunks required to fill it.
If there are many messages in a single input chunk, the extra strings will be sliced over and over to smaller parts. Slice in lua is a copy. This has a cost of O(m * n) where m is number of messages in chunk and n is chunk length.
These costs are compounded by the high cost of lua string interning that is done on every new string.
To solve the first problem we came up with a backwards compatible design that adds a new merger option. If options.scan is set in coro-net then this scan function will be used to efficiently merge several input chunks before passing them to the decoder. This brings the cost to decode down since the concat is done once as a single linear copy.
The second problem is a little harder and requires a breaking change to the decoder interface.
Before decode was decode(chunk) -> item, extra where chunk was the entire input chunk and extra was a new string of leftover bytes. By changing this to be offset based, we can avoid most the copies. Now decode is decode(chunk, index) -> item, index. Index is the position to start reading chunk and the returning index is the position to start reading on the next decode pass. This brings down the cost to just a linear scan of the input without extra copies. There is a copy at the end if there is extra data leftover that spans two input chunks. Use the above merger tool if this is common in your protocol.
Since the decode change is a breaking change, the two codecs websocket-codec and http-codec needed to be ported to the new interface. This meant major version changes in anything that accepted codecs from the user. But libraries that use codecs internally, but keep the same external interface only bumped the middle semver number.
lduboeuf
commented
7 years ago
This change is the result of a conversation on IRC.
The current decoder spec used by coro-net, coro-channel, http-codec, websocket-codec, etc causes a lot of unnecessary copies of network data.
In particular there are some problem areas with the decoder interface which requires the input chunk to start at index 1 and requires returning the full extra buffer as a new string.
O(m * n)wheremis total message length andnis number of chunks required to fill it.O(m * n)wheremis number of messages in chunk andnis chunk length.These costs are compounded by the high cost of lua string interning that is done on every new string.
To solve the first problem we came up with a backwards compatible design that adds a new merger option. If
options.scanis set in coro-net then this scan function will be used to efficiently merge several input chunks before passing them to the decoder. This brings the cost to decode down since the concat is done once as a single linear copy.The second problem is a little harder and requires a breaking change to the decoder interface.
Before decode was
decode(chunk) -> item, extrawhere chunk was the entire input chunk and extra was a new string of leftover bytes. By changing this to be offset based, we can avoid most the copies. Now decode isdecode(chunk, index) -> item, index. Index is the position to start reading chunk and the returning index is the position to start reading on the next decode pass. This brings down the cost to just a linear scan of the input without extra copies. There is a copy at the end if there is extra data leftover that spans two input chunks. Use the above merger tool if this is common in your protocol.Since the decode change is a breaking change, the two codecs
websocket-codecandhttp-codecneeded to be ported to the new interface. This meant major version changes in anything that accepted codecs from the user. But libraries that use codecs internally, but keep the same external interface only bumped the middle semver number.