See Make Map length run in O(1) instead of O(n) · Issue #12866 · ocaml/ocaml · GitHub and the links therein for discussion upstream related to changing the representation of Set and Map to make cardinal O(1).
See also [ANN] First release of baby for a related library by @fpottier.
Cheers,
Nicolas