haskell / haskell/lsp

Optimize `instance Eq NormalizedFilepath`?!

Open
#629 8 comments 1 reaction 0 assignees View on GitHub
Dominant language
Haskell
Stars
423
Forks
105
PR merge metrics
No merged PRs in 30d

Description

https://github.com/haskell/lsp/blob/774f0e9de79f6136eedbf96f5589f86f4d3a8cdb/lsp-types/src/Language/LSP/Protocol/Types/Uri.hs#L201-L202

https://github.com/haskell/lsp/blob/774f0e9de79f6136eedbf96f5589f86f4d3a8cdb/lsp-types/src/Language/LSP/Protocol/Types/Uri.hs#L56-L57

I was looking at some `-ddump-simpl` output from `ghcide` and noticed that `(==)` for `NormalizedFilePath` is somewhat unwieldy. In this case we compare two `NormalizedFilePath`s named `a1` and `b1`:

```
case a1 of { NormalizedFilePath ww2 ww3 ww4 ww5 ->
case ww2 of { NormalizedUri ww6 ww7 ->
case ww7 of { Text bx4 bx5 bx6 ->
case b1 of { NormalizedFilePath ww8 ww9 ww10 ww11 ->
case ww8 of { NormalizedUri ww12 ww13 ->
case ww13 of { Text bx3 bx7 bx8 ->
case ==# ww6 ww12 of {
__DEFAULT -> (# _| #) @ZeroBitRep @LiftedRep @(# #) @Target (##);
1# ->
case ==# bx6 bx8 of {
__DEFAULT -> (# _| #) @ZeroBitRep @LiftedRep @(# #) @Target (##);
1# ->
case compareByteArrays# bx4 bx5 bx3 bx7 bx6 of {
__DEFAULT ->
(# _| #) @ZeroBitRep @LiftedRep @(# #) @Target (##);
0# ->
case ==# ww5 ww11 of {
__DEFAULT ->
(# _| #) @ZeroBitRep @LiftedRep @(# #) @Target (##);
1# ->
case compareByteArrays# ww3 ww4 ww9 ww10 ww5 of {
__DEFAULT ->
(# _| #) @ZeroBitRep @LiftedRep @(# #) @Target (##);
0# ->
(# |_ #) @ZeroBitRep @LiftedRep @(# #) @Target wild2
```

The steps are:

1. Compare the hashes stored in the `NormalizedUri`s
2. Compare the lengths of the `Text` fields inside the `NormalizedUri`s
3. Compare the `ByteArray`s of the same `Text` fields
4. Compare the lengths of the unpacked `Text` fields in the `NormalizedFilePath`s
5. Compare the `ByteArray`s of these `Text` fields

The first step of comparing the hashes is especially useless in the context of a `HashMap` or `HashSet` operation: These operations only check for equality _after_ asserting that the hashes are the same!

It also seems that it should be possible to get away with comparing only one of the `Text` fields, right? IIUC the `NormalizedUri` is basically `internalNormalizedFilePathToUri nfp`, where `nfp` is the NFP `Text` field.

So how about this?!

```
NormalizedFilePath _uri1 nfp1 == NormalizedFilePath _uri2 nfp2 = nfp1 == nfp2
```

Contributor guide

Open the contributing guide

Research direction

Start with the two referenced sections of lsp-types/src/Language/LSP/Protocol/Types/Uri.hs and inspect the Eq instances for NormalizedFilePath and NormalizedUri. Compare the existing and proposed equality behavior, then check -ddump-simpl output and HashMap or HashSet use cases; done means equality remains correct while avoiding unnecessary comparisons.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
devtools
Issue type
Refactor
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.