Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add String.{Set,Map,Tbl} ? #8510

Open
nojb opened this Issue Mar 16, 2019 · 6 comments

Comments

Projects
None yet
5 participants
@nojb
Copy link
Contributor

commented Mar 16, 2019

This issue corresponds to PR #2302, where I proposed to add submodules String.Set and String.Map defined in the obvious way. One can also consider String.Tbl for hash tables. I am opening this issue to discuss the approach before focusing on the implementation.

The main technical objection in the linked PR was that doing so introduces a dependency between String and Set (and Map and Hashtbl) which causes these latter modules to be linked in even if we are not using the submodules in question.

To handle this I propose to introduce auxiliary modules in the stdlib, say CamlinternalStringSet, with the following contents:

include Set.Make (struct type t = string let compare = compare end)

Then in string.ml{,i} we write:

module Set = CamlinternalStringSet

The advantage of doing it this way is that thanks to the magic of module aliases, using String would not automatically result in linking Set (or Map or Hashtbl).

It is a bit ugly and haven't yet checked how this will show up in the ocamldoc-generator docs, but it solves the linking problem.

Opinions on this approach?

@nojb nojb added the stdlib label Mar 16, 2019

@trefis

This comment has been minimized.

Copy link
Contributor

commented Mar 18, 2019

I don't have any objection to this approach, but I also have no idea what the generated docs will look like.

@let-def

This comment has been minimized.

Copy link
Contributor

commented Mar 18, 2019

Add type annotation to benefit from specialization:

include Set.Make (struct type t = string let compare : string -> string -> int = compare end)
@nojb

This comment has been minimized.

Copy link
Contributor Author

commented Mar 18, 2019

Add type annotation to benefit from specialization:

include Set.Make (struct type t = string let compare : string -> string -> int = compare end)

Indeed, good point.

@mshinwell

This comment has been minimized.

Copy link
Contributor

commented Mar 18, 2019

I'm not convinced that this extra complexity is necessary, for two reasons. Firstly, the amount of code being pulled in seems really small (I think it's less than 15Kbytes on amd64, for example). Secondly, we have some ideas to get native dead code elimination working more effectively, with a lower overhead than the existing Flambda+LTO implementation.

I would also suggest that if improvements are going to be made to this area in the standard library that it is worth talking to @sliquister first. I believe he has detailed knowledge as to the various iterations we've been through at Jane Street over the years with set and map modules, concluding with the current design in Base.

@nojb

This comment has been minimized.

Copy link
Contributor Author

commented Mar 18, 2019

I would also suggest that if improvements are going to be made to this area in the standard library that it is worth talking to @sliquister first. I believe he has detailed knowledge as to the various iterations we've been through at Jane Street over the years with set and map modules, concluding with the current design in Base.

Any input you may have on this topic is warmly welcome, @sliquister.

@sliquister

This comment has been minimized.

Copy link
Contributor

commented Mar 19, 2019

In the core interface, the main reason for Map.Make and similar functors is to provide a type of map that has [@@deriving of_sexp] (as that needs a comparison baked-in to build the map). In base, [@@deriving of_sexp] is made to work some other way, and so the functors are not needed, and we removed them and their applications in String/Int/etc to reduce cross modules dependencies, for faster build, and smaller exes in the small (and also it avoids special-casing Base.Map, custom maps can be used exactly the same as Base.Map).

I suspect not applying several functors per compilation units also has benefits in terms of cmt size, typing time, doc size and runtime cost at toplevel, but I don't have evidence for that.

The alias trick suggested here certainly helps, though it seems highly annoying to write (camlinternalint32set.ml, camlinternalint32map.ml, camlinternalint32tbl.ml, then int64, then string, etc), and might make stack traces rather ugly.

@nojb nojb added the feature-wish label Mar 20, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.