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

Implement compare for bytearray #771

Merged
merged 6 commits into from
Jan 22, 2025

Conversation

mattisboeckle
Copy link
Contributor

@mattisboeckle mattisboeckle commented Jan 10, 2025

Fixes #748

@mattisboeckle mattisboeckle changed the title Implement compare for bytearray (#748) Implement compare for bytearray Jan 10, 2025
@mattisboeckle mattisboeckle marked this pull request as draft January 10, 2025 20:06
@mattisboeckle mattisboeckle force-pushed the llvm-bytestring-compare branch 3 times, most recently from 25277d2 to 469ae81 Compare January 14, 2025 09:11
@jiribenes
Copy link
Contributor

Hey, what are the next steps of this PR? We could either:

  1. Review and merge this now, then handle the Effekt bindings (+ a few tests) in a followup PR
  2. Add the Effekt bindings (+ tests) first here, then proceed with review and merge

@b-studios
Copy link
Collaborator

rough draft

extern def compare(b1: ByteArray, b2: ByteArray): Ordering = 
  llvm { llvm::compare(b1).... }

namespace llvm {

  extern def compare(b1: ByteArray, b2: ByteArray): Int
}

@jiribenes
Copy link
Contributor

jiribenes commented Jan 14, 2025

We'll also probably need to add it for JS, it should be roughly something like, uuuh:

function compareUint8Arrays(arr1, arr2) {
  const len = Math.min(arr1.length, arr2.length);
  
  for (let i = 0; i < len; i++) {
    if (arr1[i] !== arr2[i]) {
      return arr1[i] < arr2[i] ? -1 : 1;
    }
  }
  
  return arr1.length - arr2.length;
}

then clamp to {-1, 0, 1}, etc...

@mattisboeckle mattisboeckle force-pushed the llvm-bytestring-compare branch from 469ae81 to 5548a6e Compare January 19, 2025 10:45
@mattisboeckle
Copy link
Contributor Author

Where should I add the JS function? In effekt_builtins.js?
There are already some similar functions there which sadly do not work for this case

@mattisboeckle mattisboeckle marked this pull request as ready for review January 19, 2025 14:40
Comment on lines +92 to +106
function bytearray$compare(arr1, arr2) {
const len = Math.min(arr1.length, arr2.length);

for (let i = 0; i < len; i++) {
if (arr1[i] !== arr2[i]) {
return arr1[i] < arr2[i] ? -1 : 1;
}
}

if (arr1.length !== arr2.length) {
return arr1.length < arr2.length ? -1 : 1;
} else {
return 0;
}
}
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why don't we first compare the length? This is supposed to be much faster.

Suggested change
function bytearray$compare(arr1, arr2) {
const len = Math.min(arr1.length, arr2.length);
for (let i = 0; i < len; i++) {
if (arr1[i] !== arr2[i]) {
return arr1[i] < arr2[i] ? -1 : 1;
}
}
if (arr1.length !== arr2.length) {
return arr1.length < arr2.length ? -1 : 1;
} else {
return 0;
}
}
function bytearray$compare(arr1, arr2) {
if (arr1.length !== arr2.length) {
return arr1.length < arr2.length ? -1 : 1;
}
const len = Math.min(arr1.length, arr2.length);
for (let i = 0; i < len; i++) {
if (arr1[i] !== arr2[i]) {
return arr1[i] < arr2[i] ? -1 : 1;
}
}
return 0;
}

Copy link
Collaborator

@b-studios b-studios Jan 22, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Am I repeating a mistake again?

Ahhh... it is inequality... I am trapped by that every time.

Comment on lines +5 to +13
def main() = {
val b1 = fromString("Hey")
val b2 = fromString("Hey")
val b3 = fromString("He")
val b4 = fromString("Heys")
println(compareByteArray(b1, b1))
println(compareByteArray(b1, b2))
println(compareByteArray(b1, b3))
println(compareByteArray(b1, b4))
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can you make sure that these test cases cover all paths in the implementation? (shorter, longer, different prefix, etc.)

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

FWIW, I'd love a test comparing [haha!] this with equality. :)

compare == 0 <=> equals == true
compare != 0 <=> equals == false

@b-studios b-studios merged commit 454c938 into effekt-lang:master Jan 22, 2025
2 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Add string comparison to LLVM backend
4 participants