<div dir="ltr">Hi Andy,<div><br></div><div>Yes, I think this recommendation is reasonable, although I'd probably reword it a little bit, because the word "guarantees" worries me a little. How about something like that:</div><div><br></div><div><span style="color:rgb(0,0,0);font-family:-webkit-standard,serif;font-size:16px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">“If a table or parser value set has a size attribute specified for it with value N, it is recommended that a compiler should choose a data plane implementation that can store (hold)  N exact, lpm, and/or ternary entries.  It does not guarantee though that an arbitrary set of N entries can always be inserted in such a table".</span><br></div><div><span style="color:rgb(0,0,0);font-family:-webkit-standard,serif;font-size:16px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><br></span></div><div><span style="color:rgb(0,0,0);font-family:-webkit-standard,serif;font-size:16px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">Note that deliberate difference between being able to hold N entries and being able to insert arbitrary N entries</span></div><div><span style="color:rgb(0,0,0);font-family:-webkit-standard,serif;font-size:16px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><br></span></div><div><span style="color:rgb(0,0,0);font-family:-webkit-standard,serif;font-size:16px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">Thanks,</span></div><div><span style="color:rgb(0,0,0);font-family:-webkit-standard,serif;font-size:16px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">Vladimir</span></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Mar 25, 2018 at 7:47 PM, Andy Fingerhut (jafinger) <span dir="ltr"><<a href="mailto:jafinger@cisco.com" target="_blank">jafinger@cisco.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">





<div lang="EN-US" link="blue" vlink="purple">
<div class="m_-8929120413442291280WordSection1">
<p class="MsoNormal"><span style="font-size:12.0pt">When you say the phrase “up to N”, do you mean the same thing as the following sentences, or do you mean something different?<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"-webkit-standard",serif;color:black">“If a table or parser value set has a size attribute specified for it with value N, it is recommended that if a compiler can choose a data plane implementation
 that guarantees that an arbitrary set of N exact, lpm, and/or ternary entries can be added, at a reasonable cost, it should do so.  However, a compiler is allowed to choose data plane implementation that can fail to add a new entry even if significantly fewer
 than N entries are currently installed.”<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"-webkit-standard",serif;color:black"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"-webkit-standard",serif;color:black">In other words, nothing is guaranteed, but there is a specific kind of recommendation given, and simultaneously a warning to people using the ‘size’ attribute
 that they are not guaranteed they can add N entries to such an object, unless they find those guarantees outside of the language spec (e.g. in their P4 vendor’s custom attributes/compiler options).<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"-webkit-standard",serif;color:black"><u></u> <u></u></span></p>
<p class="MsoNormal">Andy<u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt"><u></u> <u></u></span></p>
<div style="border:none;border-top:solid #b5c4df 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="font-size:12.0pt;color:black">From: </span></b><span style="font-size:12.0pt;color:black">Vladimir Gurevich <<a href="mailto:vag@barefootnetworks.com" target="_blank">vag@barefootnetworks.com</a>><br>
<b>Date: </b>Sunday, March 25, 2018 at 7:37 PM</span></p><div><div class="h5"><br>
<b>To: </b>"Andy Fingerhut (jafinger)" <<a href="mailto:jafinger@cisco.com" target="_blank">jafinger@cisco.com</a>><br>
<b>Cc: </b>Mihai Budiu <<a href="mailto:mbudiu@vmware.com" target="_blank">mbudiu@vmware.com</a>>, p4-design <<a href="mailto:p4-design@lists.p4.org" target="_blank">p4-design@lists.p4.org</a>><br>
<b>Subject: </b>Re: [P4-design] Maybe too much text describing issues around P4 table and parser value set sizes<u></u><u></u></div></div><p></p>
</div><div><div class="h5">
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal"><a name="m_-8929120413442291280__MailOriginalBody">Hi Andy, <u></u><u></u></a></p>
<div>
<p class="MsoNormal"><span><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>I think that your article is a great explanation and with "up to N" clause I think it provides a totally usable definition that is understandable by most people. I was responding to Mihai's suggestion
 that because we can't have a "formal" definition of "size" it's better to leave it alone.<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>Thanks,<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>Vladimir<u></u><u></u></span></p>
</div>
</div>
<div>
<p class="MsoNormal"><span><u></u> <u></u></span></p>
<div>
<p class="MsoNormal"><span>On Sun, Mar 25, 2018 at 7:34 PM, Andy Fingerhut (jafinger) <</span><a href="mailto:jafinger@cisco.com" target="_blank"><span>jafinger@cisco.com</span><span></span></a><span>>
 wrote:<u></u><u></u></span></p>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal"><span><span style="font-size:12.0pt">Vladimir, do you have a specific recommendation on what you think the language spec should say about
 the ‘size’ table attribute?  That is what I was going for in part of my most recent message, and I don’t think it was trying to tie the hands of implementers much at all.</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:12.0pt"> </span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:12.0pt">Andy</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:12.0pt"> </span><u></u><u></u></span></p>
<div style="border:none;border-top:solid #b5c4df 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><span><b><span style="font-size:12.0pt;color:black">From:
</span></b></span><span><span style="font-size:12.0pt;color:black">Vladimir Gurevich <</span></span><a href="mailto:vag@barefootnetworks.com" target="_blank"><span><span style="font-size:12.0pt">vag@barefootnetworks.com</span></span><span></span></a><span><span style="font-size:12.0pt;color:black">><br>
<b>Date: </b>Sunday, March 25, 2018 at 7:31 PM<br>
<b>To: </b>"Andy Fingerhut (jafinger)" <</span></span><a href="mailto:jafinger@cisco.com" target="_blank"><span><span style="font-size:12.0pt">jafinger@cisco.com</span></span><span></span></a><span><span style="font-size:12.0pt;color:black">><br>
<b>Cc: </b>Mihai Budiu <</span></span><a href="mailto:mbudiu@vmware.com" target="_blank"><span><span style="font-size:12.0pt">mbudiu@vmware.com</span></span><span></span></a><span><span style="font-size:12.0pt;color:black">>,
 p4-design <</span></span><a href="mailto:p4-design@lists.p4.org" target="_blank"><span><span style="font-size:12.0pt">p4-design@lists.p4.org</span></span><span></span></a><span><span style="font-size:12.0pt;color:black">></span><u></u><u></u></span></p>
<div>
<div>
<p class="MsoNormal"><span><br>
<b>Subject: </b>Re: [P4-design] Maybe too much text describing issues around P4 table and parser value set sizes<u></u><u></u></span></p>
</div>
</div>
</div>
<div>
<div>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span><a name="m_-8929120413442291280_m_2542334610138196156__MailOriginalBody">Hello,
</a><u></u><u></u></span></p>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>I think we need to re-state the basic goals of our activities. Specifically<u></u><u></u></span></p>
</div>
<div>
<ol start="1" type="1">
<li class="MsoNormal">
<span>Are we trying to define a super-formal language that will allow one to create not only super-portable programs, but even super-portable APIs that control those programs to the extent that you can swap targets (ranging
 from high-speed ASICs to fully SW implementations and anything in-between) as easily as one swaps one pair of gloves for another
<b>or</b> <u></u><u></u></span></li><li class="MsoNormal">
<span>Are we trying to define a practical language that would allow people to easily create data plane programs on target device of their choice and generate a corresponding control plane API? <u></u><u></u></span></li></ol>
<div>
<p class="MsoNormal"><span>I think that goal #2 is quite achievable, but the goal #1 is, unfortunately, not. Moreover, trying to get closer to goal #1 will probably
 take us further away from being able to define a practical, usable language that gives data plane designers the ability to get things done. <u></u><u></u></span></p>
</div>
</div>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>I totally agree that it is impossible to formally define what "size" is. The question is: should that preclude us from moving forward
 and having this in the language? Even in Euclidian geometry there are terms that are not defined, e.g a point and a straight line. That's ok. Having "size" and, perhaps, other similar attributes in the language makes programs generally more readable and understandable.
 In fact, it even makes them more target-independent and more suitable for optimization, because it would not require people to use the externs, requiring a very specific implementation (as you suggested). <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>I can certainly see the value of implementation externs, especially if they would allow us to use fewer annotations, but unfortunately
 they will not, because any real implementation(e.g. for hash-tables) will require you to specify anywhere from one to dozens of parameters per table, most of of them optional -- something externs are not very good at (not to mention that it would be nice if
 they were named). <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>I urge everyone to keep P4 a practical language and sometimes that means that we might need to have things there that we might not be
 able to formally define. That's OK. <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>Thanks,<br>
Vladiimir<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
</div>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<div>
<p class="MsoNormal"><span>On Sun, Mar 25, 2018 at 5:55 PM, Andy Fingerhut (jafinger) <</span><a href="mailto:jafinger@cisco.com" target="_blank"><span>jafinger@cisco.com</span><span></span></a><span>>
 wrote:<u></u><u></u></span></p>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0in;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal"><span><span style="font-size:12.0pt">If ‘size’ were an integer that meant, ‘the compiler will implement this table with something that can
 in some cases install up to N entries, but how likely being able to reach N entries is implementation- and table-specific’, then the value of N could be used as the “raw capacity” of a hash table, for example.</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:12.0pt"> </span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:12.0pt">This might be what Vladimir means when he says “up to N”.  It seems a bit odd to me for an implementation
 to use, say, a size of 16384 for a hash table if then takes that value and uses it as the raw theoretical maximum capacity of a hash table, where in practice that could mean that adding a set of 12,000 keys causes the 12,000<sup>th</sup> one to fail to add
 because of too many collisions with earlier added entries.  75% to 95% typical usable capacity from a medium to large hash table is about the best I’ve seen (where the actual fraction depends on the raw size, how many hash functions, overflow TCAM size used,
 if any, etc.).</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:12.0pt"> </span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:12.0pt">I think it would be reasonable to define ‘size’ to take an integer type value in the language spec, and
 leave the meaning of how that value is used up to the implementation, with just a general guideline of “it is recommended if you can make a table / parser value set that guarantees that many exact, lpm, and/or ternary entries can be added, but an implementation
 is allowed to use implementations that can fail to add entries at lower number of entries than the given size’.</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:12.0pt"> </span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:12.0pt">Andy</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:12.0pt"> </span><u></u><u></u></span></p>
<div style="border:none;border-top:solid #b5c4df 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><span><b><span style="font-size:12.0pt;color:black">From:
</span></b></span><span><span style="font-size:12.0pt;color:black">Mihai Budiu <</span></span><a href="mailto:mbudiu@vmware.com" target="_blank"><span><span style="font-size:12.0pt">mbudiu@vmware.com</span></span><span></span></a><span><span style="font-size:12.0pt;color:black">><br>
<b>Date: </b>Sunday, March 25, 2018 at 5:17 PM<br>
<b>To: </b>"Andy Fingerhut (jafinger)" <</span></span><a href="mailto:jafinger@cisco.com" target="_blank"><span><span style="font-size:12.0pt">jafinger@cisco.com</span></span><span></span></a><span><span style="font-size:12.0pt;color:black">>,
 Vladimir Gurevich <</span></span><a href="mailto:vag@barefootnetworks.com" target="_blank"><span><span style="font-size:12.0pt">vag@barefootnetworks.com</span></span><span></span></a><span><span style="font-size:12.0pt;color:black">><br>
<b>Cc: </b>p4-design <</span></span><a href="mailto:p4-design@lists.p4.org" target="_blank"><span><span style="font-size:12.0pt">p4-design@lists.p4.org</span></span><span></span></a><span><span style="font-size:12.0pt;color:black">><br>
<b>Subject: </b>RE: [P4-design] Maybe too much text describing issues around P4 table and parser value set sizes</span><u></u><u></u></span></p>
</div>
<div>
<div>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
<p class="MsoNormal"><span>The conclusion is that it is impossible to give a simple description of the meaning of “size”.<u></u><u></u></span></p>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<p class="MsoNormal"><span>There are two possibilities going forward:<u></u><u></u></span></p>
<ul type="disc">
<li class="MsoNormal">
<span>We specify in the spec that the tables and value_sets can have a size integer parameter, but the meaning is target-dependent<u></u><u></u></span></li><li class="MsoNormal">
<span>We do not standardize these at all. Tables can still have a size parameter (it is not mandated or forbidden by the spec, as it is today), but each target can choose a different way to specify sizes. An example is
 given below. For value_sets we have to use an annotation.<u></u><u></u></span></li></ul>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<p class="MsoNormal"><span>For tables I will submit again the example in ebpf_model, which is perfect for this particular target:<u></u><u></u></span></p>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">/*</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">Each table must have an implementation property which is either an array_table</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">or a hash_table.</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">*/</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New""> </span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">/**</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">Implementation property for tables indicating that tables must be implemented</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">using EBPF array map.</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">*/</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">extern array_table {</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">    /// @param size: maximum number of entries in table</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">    array_table(bit<32> size);</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">}</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New""> </span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">/**</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">Implementation property for tables indicating that tables must be implemented</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">using EBPF hash map.</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">*/</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">extern hash_table {</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">    /// @param size: maximum number of entries in table</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">    hash_table(bit<32> size);</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">}</span><u></u><u></u></span></p>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">table t {</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">   keys = …</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">   implementation = hash_table(32);</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:10.0pt;font-family:"Courier New"">}</span><u></u><u></u></span></p>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<p class="MsoNormal"><span>The benefit of this approach is that an architecture can define whatever parameters it deems necessary for describing the implementation.
 If Vladimir likes max_size, min_size, average_size and other parameters, he can define an extern which has all these as constructor arguments for his architecture.<u></u><u></u></span></p>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<p class="MsoNormal"><span>The downside is that this is certainly target-specific, and thus non-portable.<u></u><u></u></span></p>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<p class="MsoNormal"><span>But it looks from Andy’s description that the portability of making size a standard feature is illusory.<u></u><u></u></span></p>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<p class="MsoNormal"><span>Mihai<u></u><u></u></span></p>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<div>
<div style="border:none;border-top:solid #e1e1e1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><span><b>From:</b> P4-design [mailto:</span><a href="mailto:p4-design-bounces@lists.p4.org" target="_blank"><span>p4-design-bounces@<wbr>lists.p4.org</span><span></span></a><span>]
<b>On Behalf Of </b>Andy Fingerhut (jafinger)<br>
<b>Sent:</b> Saturday, March 24, 2018 5:10 PM<br>
<b>To:</b> Vladimir Gurevich <</span><a href="mailto:vag@barefootnetworks.com" target="_blank"><span>vag@barefootnetworks.com</span><span></span></a><span>><br>
<b>Cc:</b> p4-design <</span><a href="mailto:p4-design@lists.p4.org" target="_blank"><span>p4-design@lists.p4.org</span><span></span></a><span>><br>
<b>Subject:</b> Re: [P4-design] Maybe too much text describing issues around P4 table and parser value set sizes<u></u><u></u></span></p>
</div>
</div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:12.0pt">If by “up to N” you mean “up to N with high probability”, or “up to N for most practical sets of keys
 you probably want to install”, yes that is what I was trying to convey in the article for hash tables.  I wasn’t trying to say that ATCAMs are any worse than hash tables in that regard (although some variations I have worked with _<i>are</i>_), just that they
 are no better in them, either.</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:12.0pt"> </span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:12.0pt">Andy</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="font-size:12.0pt"> </span><u></u><u></u></span></p>
<div style="border:none;border-top:solid #b5c4df 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><span><b><span style="font-size:12.0pt;color:black">From:
</span></b></span><span><span style="font-size:12.0pt;color:black">Vladimir Gurevich <</span></span><a href="mailto:vag@barefootnetworks.com" target="_blank"><span><span style="font-size:12.0pt">vag@barefootnetworks.com</span></span><span></span></a><span><span style="font-size:12.0pt;color:black">><br>
<b>Date: </b>Saturday, March 24, 2018 at 4:36 PM<br>
<b>To: </b>"Andy Fingerhut (jafinger)" <</span></span><a href="mailto:jafinger@cisco.com" target="_blank"><span><span style="font-size:12.0pt">jafinger@cisco.com</span></span><span></span></a><span><span style="font-size:12.0pt;color:black">><br>
<b>Cc: </b>p4-design <</span></span><a href="mailto:p4-design@lists.p4.org" target="_blank"><span><span style="font-size:12.0pt">p4-design@lists.p4.org</span></span><span></span></a><span><span style="font-size:12.0pt;color:black">><br>
<b>Subject: </b>Re: [P4-design] Maybe too much text describing issues around P4 table and parser value set sizes</span><u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span><a name="m_-8929120413442291280_m_2542334610138196156_m_5328737003457425">Hi Andy,
<u></u><u></u></a></span></p>
<div>
<p class="MsoNormal"><span><span> <u></u><u></u></span></span></p>
</div>
<div>
<p class="MsoNormal"><span><span>I totally agree that the practical ATCAM capacity from the control
 plane point of view (e.g. how many routes you can put into a ATCAM with N entries divided into M partitions) is difficult to predict, but "up to N" statement can still be holding some water :) I think that this is an inherent ATCAM property, much like the
 fact that you can't generally guarantee any specific occupancy for a hashed table (as you clearly outlined in the article).<u></u><u></u></span></span></p>
</div>
<div>
<p class="MsoNormal"><span><span> <u></u><u></u></span></span></p>
</div>
<div>
<p class="MsoNormal"><span><span>Thanks,<u></u><u></u></span></span></p>
</div>
<div>
<p class="MsoNormal"><span><span>Vladmir<u></u><u></u></span></span></p>
</div>
</div>
<div>
<p class="MsoNormal"><span><span> <u></u><u></u></span></span></p>
<div>
<p class="MsoNormal"><span><span>On Sat, Mar 24, 2018 at 10:40 AM, Andy Fingerhut (jafinger) <</span></span><a href="mailto:jafinger@cisco.com" target="_blank"><span><span>jafinger@cisco.com</span></span><span><span></span></span></a><span><span>>
 wrote:<u></u><u></u></span></span></p>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0in;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal"><span><span><span style="font-size:12.0pt">Thanks for the comments, Vladimir. 
 I agree with just about every word, and would be happy to incorporate your comments into it, perhaps in another week or so after I get some other things done.</span><u></u><u></u></span></span></p>
<p class="MsoNormal"><span><span><span style="font-size:12.0pt"> </span><u></u><u></u></span></span></p>
<p class="MsoNormal"><span><span><span style="font-size:12.0pt">One quick response here.  The article
 does not say that algorithmic TCAMs are not “fast”.  It says: ‘All techniques I am aware of here either cannot go "fast" as defined above, or have capacity that is dependent upon the contents of the table entries.’.  If you know of an algorithmic TCAM method
 that is both fast _and_ has capacity independent of the contents of the table entries, then I really want to hear about it.  I’ve spent way too much of my life dealing with the non-deterministic capacity of algorithmic TCAMs, for Cisco platforms where they
 wish they could claim the capacity was a fixed number N.</span><u></u><u></u></span></span></p>
<p class="MsoNormal"><span><span><span style="font-size:12.0pt"> </span><u></u><u></u></span></span></p>
<p class="MsoNormal"><span><span><span style="font-size:12.0pt">Thanks,</span><u></u><u></u></span></span></p>
<p class="MsoNormal"><span><span><span style="font-size:12.0pt">Andy</span><u></u><u></u></span></span></p>
<p class="MsoNormal"><span><span><span style="font-size:12.0pt"> </span><u></u><u></u></span></span></p>
<div style="border:none;border-top:solid #b5c4df 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><span><span><b><span style="font-size:12.0pt;color:black">From:
</span></b></span></span><span><span><span style="font-size:12.0pt;color:black">Vladimir Gurevich <</span></span></span><a href="mailto:vag@barefootnetworks.com" target="_blank"><span><span><span style="font-size:12.0pt">vag@barefootnetworks.com</span></span></span><span><span></span></span></a><span><span><span style="font-size:12.0pt;color:black">><br>
<b>Date: </b>Saturday, March 24, 2018 at 9:06 AM<br>
<b>To: </b>"Andy Fingerhut (jafinger)" <</span></span></span><a href="mailto:jafinger@cisco.com" target="_blank"><span><span><span style="font-size:12.0pt">jafinger@cisco.com</span></span></span><span><span></span></span></a><span><span><span style="font-size:12.0pt;color:black">><br>
<b>Cc: </b>p4-design <</span></span></span><a href="mailto:p4-design@lists.p4.org" target="_blank"><span><span><span style="font-size:12.0pt">p4-design@lists.p4.org</span></span></span><span><span></span></span></a><span><span><span style="font-size:12.0pt;color:black">><br>
<b>Subject: </b>Re: [P4-design] Maybe too much text describing issues around P4 table and parser value set sizes</span><u></u><u></u></span></span></p>
</div>
<div>
<div>
<div>
<p class="MsoNormal"><span><span> <u></u><u></u></span></span></p>
</div>
<div>
<p class="MsoNormal"><span><span>Hi Andy,
</span><u></u><u></u></span></p>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>Great stuff, worthy of a book chapter or an encyclopedia article.<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>If anything, I'd just say that some of the assumptions are a little "rosy" meaning that they cover the "classic" behaviors, but do not
 account for a variety of idiosyncratic behaviors that are often encountered in real life. Call them bugs, features or both, but they do have an effect on table capacity. One big topic you sort of omitted is the question of how to count default actions: are
 they entries or not? do they need to be included in total entry count or not (i.e. should the "natural" size be 2^N, 2^N-1 or 2^N+1)? Even in "good" cases, such as TCAMs or indexed tables, I am sure that different implementations will answer this question
 differently. In other cases control plane might need to reserve additional entries for a variety of technical/efficiency reasons (faster entry moves in TCAMs, atomic updates, garbage collection (in action profiles), etc.). <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>Therefore, people usually advertise their table capacities as being "up to N entries", with that "up to" being the key, that allows
 customers to reasonably judge the device capacity, while freeing the vendors from frivolous lawsuits :)<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>I know, there are different opinions in this area (mostly guided by (a) the n-to-1 case you described and (b) the fact that SW implementations
 might not need size indication at all), but coming from the ASIC background, I firmly believe that the basic "up to" size attribute is vital for both tables and value_sets and is preferred to an annotation, because it expresses a basic intent of the data plane
 program designer that the compiler cannot reasonably guess (as opposed to many technical allocation parameters (e.g. the number of ways in a hash table) that the compilers can determine automatically, often even better than humans). P4_14 even has min_size
 and max_size attributes in addition to size and I think that was not a bad idea (although I am not sure if they were implemented anywhere). <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>Last, but not least, I am not quite sure what to make of the comment at the end of the article that assert that ATCAMs are not "fast".
 I think everything depends on the implementation, but if you can implement a multi-way hash table with O(1) lookup performance, there is no reason why you can't implement an ATCAM with the same performance either. <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>Happy hacking,<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span>Vladimir<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
</div>
<div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<div>
<p class="MsoNormal"><span>On Fri, Mar 23, 2018 at 9:49 PM, Andy Fingerhut (jafinger) <</span><a href="mailto:jafinger@cisco.com" target="_blank"><span>jafinger@cisco.com</span><span></span></a><span>>
 wrote:<u></u><u></u></span></p>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0in;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal"><span>In the last P4 language design WG meeting, I volunteered to write up some notes on P4 table sizes, and what “size” might mean.<u></u><u></u></span></p>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<p class="MsoNormal"><span>I have written up a discussion of the issues around P4 table and parser value set sizes here.  It is more a tutorial style directed
 at people who might be unfamiliar with issues around high speed implementations of P4-style matching, and what their consequences are for specifying table sizes, especially ones where the actual capacity of a table is not really predictable.<u></u><u></u></span></p>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<p class="MsoNormal"><span></span><a href="https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_jafingerhut_p4-2Dguide_blob_master_docs_p4-2Dtable-2Dand-2Dparser-2Dvalue-2Dset-2Dsizes.md&d=DwMGaQ&c=uilaK90D4TOVoH58JNXRgQ&r=tGW6TKXajnoXSyy1S1P4DHGPe8sj54GGvw-b21n7aWg&m=igHNDkIsLYagXgGCPpIvkY56e6q_4mGo3TN4g8WOQYk&s=Mm_IWg6WCXnjrb1Vh5lONc_7WE2uO3BgmENj5HnM_BQ&e=" target="_blank"><span>https://github.com/<wbr>jafingerhut/p4-guide/blob/<wbr>master/docs/p4-table-and-<wbr>parser-value-set-sizes.md</span><span></span></a><span><u></u><u></u></span></p>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
<p class="MsoNormal"><span>Corrections/questions/comments welcome.<u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="color:#888888"> </span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="color:#888888">Andy</span><u></u><u></u></span></p>
<p class="MsoNormal"><span><span style="color:#888888"> </span><u></u><u></u></span></p>
</div>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span><br>
______________________________<wbr>_________________<br>
P4-design mailing list<br>
</span><a href="mailto:P4-design@lists.p4.org" target="_blank"><span>P4-design@lists.p4.org</span><span></span></a><span><br>
</span><a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.p4.org_mailman_listinfo_p4-2Ddesign-5Flists.p4.org&d=DwMGaQ&c=uilaK90D4TOVoH58JNXRgQ&r=tGW6TKXajnoXSyy1S1P4DHGPe8sj54GGvw-b21n7aWg&m=igHNDkIsLYagXgGCPpIvkY56e6q_4mGo3TN4g8WOQYk&s=Avv9VPJx5NI3SRUQy9aN7lk_rDLuHqX0_IwMBoDIA2E&e=" target="_blank"><span>http://lists.p4.org/mailman/<wbr>listinfo/p4-design_lists.p4.<wbr>org</span><span></span></a><span><u></u><u></u></span></p>
</blockquote>
</div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><span> <u></u><u></u></span></p>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><span><u></u> <u></u></span></p>
</div>
</div></div></div>
</div>

</blockquote></div><br></div>