bsc regression in Typecheck/internal with large enums

[czeck]

I observed a regression in bsc, between commits 88d4eef and 67161ca (Merge pull request #284 from krame505/generics)
The behavior is that typecheck is much slower and that Internal hangs as the size of an enum grows.

A reduced test case is attached. This can be run with
bsc -v IPv4.bsv
enums.zip

[quark17]

Thanks! Issue #334 was opened because we'd noticed a slowdown with the testsuite, but had not identified any single test (or tests) yet.

[quark17]

It's worth noting that PR #341 made a significant fix to efficiency, so it's worth comparing at or after that merge. Although the fix was not related to large enums, so even with the HEAD I do still see time spent in typecheck (40-ish seconds) and internal (150 seconds). And I do confirm that at 88d4eef it compiles in under a second.

[quark17]

I don't know if anyone has time to look at this, so it may fall me to. But I briefly mentioned it to @krame505 and our instincts are that it has to do with that, for an enum with N tags, there are N nested pattern/constructor applications, each with a type containing up to N Either constructors. This would result in an O(n^2) overhead in type checking for the Generic instance.

One conceivable fix would be to "flatten" the chain of Eithers into a balanced binary tree, giving O(n log n) type checking overhead for the instance. This would require changing some generic instances that rely on all Left type parameters being Conc types. However having the representations structured in this way could actually be useful for doing serialization, as the chain of Left/Right constructors would directly correspond to 1s and 0s in the tag.

[quark17]

A workaround might be to exempt the enum type from the generics mechanism by defining an explicit null instance. For example, the package compiles instantly when I add this (causing BSC not to derive an instance):

instance Generic#(IPProtocol, Conc#(IPProtocol));
  function from(v) = tagged Conc v;
  function to(x) = case (x) matches
                     tagged Conc .v : v;
                   endcase;
endinstance

However, I don't know if this would cause problems when the type is used in real code (which this file doesn't illustrate). It could cause recursion: when a typeclass is implemented generic-ly, it has a fall-through default that attempts to use the generic-based instance if no concrete instance is found; but if the generic instance finds Conc, then it may recurse by going back to the original instance and looking for a concrete instance; if you haven't written a concrete instance, then typeclass resolution will fall back on the generic-based default instance, and loop. An alternative way to write the Generic instance, to avoid looping, would be to declare that the enum is a primitive, and therefore not to recurse on it:

instance Generic#(IPProtocol, ConcPrim#(IPProtocol));
  function from(v) = tagged ConcPrim v;
  function to(x) = case (x) matches
                     tagged ConcPrim .v : v;
                   endcase;
endinstance

The Generic instance is used internally by BSC for implicit condition lifting and per-field handling of undefined and uninitialized values, but since enums do not have subfields, I think it would be OK. In implementing generics, we had discussed having a feature in the syntax for telling BSC that you don't want to auto-derive Generic; in that case, BSC could derive explicit instances for its internally-used typeclasses (which would guarantee no problem).

There are certain expectations on the form of the Generic representation, and I didn't know if, say, the Conc instance was meeting that expectation or would need to be wrapped in MetaData (and possibly use a dummy Conc type). I thought that I would test this using the CShow package (like FShow but displays BH/Classic syntax, and it is built using generics). I see, though, that CShow doesn't expect to handle ConcPrim, and expects that they should have explicit instances defined. (I don't know if it's better for CShow to abort like this, alerting us that we need to add an instance for a prim; or whether it ought to have a arm that matches this and just prints <prim> or something in that spot.)

One thing to try might be use Conc but not make it recursive:

instance Generic#(IPProtocol, Meta#(MetaData#("IPProtocol", "IPv4", PrimUnit, 1),
                                    Meta#(MetaConsAnon#("IPProtocol", 0, 1),
                                          Meta#(MetaField#("x", 0),
                                                Conc#(Bit#(8))))));
  function from(v) = tagged Meta (tagged Meta (tagged Meta (tagged Conc (pack(v)))));
  function to(x) = case (x) matches
                     tagged Meta (tagged Meta (tagged Meta (tagged Conc .bs))) : unpack(bs);
                   endcase;
endinstance

Hm, yes, actually, something like this last one might be best. Here I've declared that the type IPProtocol is equivalent to a type with one constructor containing a Bit#(8) type. If I define a testbench using CShow:

(* synthesize *)
module mkTest ();
  Reg#(IPProtocol) rg <- mkReg(UDPLite);
  rule r;
    $display(cshow(rg));
    $finish(0);
  endrule
endmodule

it displays the type like this:

IPProtocol 0x88

You might be able to define the representation with less meta data, such that its representation is just Conc#(Bit#(8)) (and cshow would just print 0x88), but probably best to keep within the expected form for derived representations.

[quark17]

The balanced binary tree of Either has been implemented and the IPv4.bsv example now compiles in a few seconds even on my old laptop. So I think this issue is resolved and I'll close the discussion, but please open an issue if you notice any remaining inefficiencies.