<div dir="ltr">Alexander -- what's the application supposed to do if it receives some packets in a non-monotonic order?  If the answer is "ignore", then you could just check that the packet ID is greater than the last packet ID and everything else just falls out naturally.<div><br></div><div><div><br></div><div>If you still need to process out-of-order packets, then consider each packet's "has been seen" value as a single bit.  There is some packet count window C beyond which duplicates are not possible.  Maintain a queue of bytes totalling at least C bits, as well as the id number at which the byte queue starts.  When a new packet comes in, if it would require using one or more new bytes, push those to the front and drop the equivalent number off the back, and update the low byte queue id.  Create a 'test byte' which has only the new bit set in the appropriate position for that byte.  use binary-and ("band") to check to see if that bit has been seen in the appropriate byte in the byte queue; if the resulting byte is greater than zero, the bit has already been seen; do whatever processing is necessary.  Otherwise, the bit has not been seen; set the bit in the byte queue, process, and continue.</div><div><br></div><div>This is probably fastest in C/C++ but Erlang should be fine as long as the sparsity factor between packet ids is not generally gigantic (i.e. it's usually 1, rarely 100).  If it's gigantic, then I'd probably use a queue of small pooled bloom filters in the same way so that I wouldn't have to do as much allocation.  As always, measure and compare.</div></div><div><br></div><div>F.</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Feb 18, 2016 at 6:58 AM, Jesper Louis Andersen <span dir="ltr"><<a href="mailto:jesper.louis.andersen@gmail.com" target="_blank">jesper.louis.andersen@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Keep a map, M :: #{ integer() => bool() } and ask if there is_key/2 on the ID's. Once in a while, you GC the map through maps:with(lists:seq(ID1, ID2), M)  and make it small again.<br><br></div>You would have to measure if this is actually faster/slower and by how much it is a slower solution. It isn't a priori given it would be either. jlouis/eministat will help determine if it is the case.<br><br></div><div class="gmail_extra"><div><div class="h5"><br><div class="gmail_quote">On Thu, Feb 18, 2016 at 2:43 PM, Alexander Petrovsky <span dir="ltr"><<a href="mailto:askjuise@gmail.com" target="_blank">askjuise@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Yep, right now I try to do something similar with bitmap and sliding window, that will shift. Could you explain about maps?<br></div><div><br></div><div>Thanks!</div></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">2016-02-18 16:37 GMT+03:00 Jesper Louis Andersen <span dir="ltr"><<a href="mailto:jesper.louis.andersen@gmail.com" target="_blank">jesper.louis.andersen@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div>A simple solution that may work in the end is to keep track of a window of bits:<br><br></div>* shift the window as the ID increases<br></div>* check older packets against the window<br><br></div>This gives you "SACK" support, is fast to check against and fast to expire old data due to the shifting.<br><br></div>Simply using an ordered list or a map could also work if you clean it up eventually. It depends on how fast your CPU core is.<br><br></div><div class="gmail_extra"><div><div><br><div class="gmail_quote">On Thu, Feb 18, 2016 at 2:24 PM, Alexander Petrovsky <span dir="ltr"><<a href="mailto:askjuise@gmail.com" target="_blank">askjuise@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Ouch, I forgot to say, the IDs can be sparse, so they not really monotonically, they just grow, and can be reordered.</div><div><div><div class="gmail_extra"><br><div class="gmail_quote">2016-02-18 16:20 GMT+03:00 Danil Zagoskin <span dir="ltr"><<a href="mailto:z@gosk.in" target="_blank">z@gosk.in</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi!<div><br></div><div>If ID grows monotinically and you have no plans of recovering after packet reordering, then you can just keep the previous ID.</div><div>  - If CurID > PrevID, CurID is unique;</div><div>  - If CurID == PrevID, it is not unique;</div><div>  - If CurID < PrevID, it is a bug or reordering, let it crash.</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote"><div><div>On Thu, Feb 18, 2016 at 3:01 PM, Alexander Petrovsky <span dir="ltr"><<a href="mailto:askjuise@gmail.com" target="_blank">askjuise@gmail.com</a>></span> wrote:<br></div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div><div dir="ltr">Hi!<div><br></div><div>I have the stream of packets with ID (int), and I need to check is the packet is uniq (by ID) or not?<div><br></div><div>Incoming rate is about 20k pps and ID is monotonically grows. What's the best way and data structure fit for this problem?</div><span><font color="#888888"><div><br></div>-- <br><div><div dir="ltr">Петровский Александр / Alexander Petrovsky,<br><br>Skype: askjuise<br><div>Phone: +7 914 8 820 815<div><br></div></div></div></div>
</font></span></div></div>
<br></div></div>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" rel="noreferrer" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
<br></blockquote></div><span><font color="#888888"><br><br clear="all"><div><br></div>-- <br><div><div dir="ltr"><div><font face="'courier new', monospace">Danil Zagoskin | <a href="mailto:z@gosk.in" target="_blank">z@gosk.in</a></font></div></div></div>
</font></span></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div><div dir="ltr">Петровский Александр / Alexander Petrovsky,<br><br>Skype: askjuise<br><div>Phone: +7 914 8 820 815<div><br></div></div></div></div>
</div>
</div></div><br>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" rel="noreferrer" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
<br></blockquote></div><br><br clear="all"><br>-- <br></div></div><span><font color="#888888"><div>J.</div>
</font></span></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div><div dir="ltr">Петровский Александр / Alexander Petrovsky,<br><br>Skype: askjuise<br><div>Phone: +7 914 8 820 815<div><br></div></div></div></div>
</div>
</div></div></blockquote></div><br><br clear="all"><br></div></div><span class="HOEnZb"><font color="#888888">-- <br><div>J.</div>
</font></span></div>
<br>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" rel="noreferrer" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
<br></blockquote></div><br></div>