I'm wondering if there is some inherit flaw in coding some data structures in Node/JS. Maybe this is just another case of the "Node tax"? Things like boxing, floating point number arithmetic, manual pop counts, array copying with bounds checks, etc would all go quite a far way to making for example the Map quite under performant by quite a significant factor especially with large collection sizes and hot loops. Have no idea what the Node runtime does/optimises for example the software version of PopCount encoded in the Immutable.js.
Having written persistent data structures in other lang's that are quite capable (170ns lookup 10,000,000 elements approx to give a rough guide) - yes it is an order slower than unordered hash mutable structures but often still faster than for example the mutable ordered ones I've tested with the advantage of still being immutable. This does benefit some scenarios where you want data sharing/cheap clones of data.
Having written persistent data structures in other lang's that are quite capable (170ns lookup 10,000,000 elements approx to give a rough guide) - yes it is an order slower than unordered hash mutable structures but often still faster than for example the mutable ordered ones I've tested with the advantage of still being immutable. This does benefit some scenarios where you want data sharing/cheap clones of data.