refactor: move bsearch function to C-code #2945
Open
+44
−32
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
d975a4c
to
9e3c7bc
Compare
emanuele6
reviewed
Nov 15, 2023
emanuele6
reviewed
Nov 15, 2023
emanuele6
reviewed
Nov 15, 2023
9e3c7bc
to
e045979
Compare
emanuele6
reviewed
Nov 15, 2023
29c1f4e
to
618c10f
Compare
|
@emanuele6 I think this is ready |
|
The |
suisanT1
approved these changes
Dec 27, 2023
4866769
to
949b647
Compare
|
@emanuele6 @itchyny I've just refactored this, and merging should be okay. |
itchyny
reviewed
Feb 5, 2024
itchyny
reviewed
Feb 5, 2024
itchyny
reviewed
Feb 5, 2024
itchyny
reviewed
Feb 5, 2024
50fc13a
to
569da27
Compare
itchyny
reviewed
Feb 7, 2024
|
I found a regression. On updating tests see my review comment above. |
a77f02a
to
42135ed
Compare
|
I think we can reduce special cases, simplify the logic. static jv f_bsearch(jq_state *jq, jv input, jv target) {
if (jv_get_kind(input) != JV_KIND_ARRAY) {
return type_error(input, "cannot be searched from");
}
int start = 0;
int end = jv_array_length(jv_copy(input));
jv answer = jv_invalid();
while (start < end) {
int mid = (start + end) / 2;
int result = jv_cmp(jv_copy(target), jv_array_get(jv_copy(input), mid));
if (result == 0) {
answer = jv_number(mid);
break;
} else if (result < 0) {
end = mid;
} else {
start = mid + 1;
}
}
if (!jv_is_valid(answer)) {
answer = jv_number(-1 - start);
}
jv_free(input);
jv_free(target);
return answer;
} |
42135ed
to
95cbcc5
Compare
itchyny
approved these changes
Feb 19, 2024
emanuele6
previously requested changes
Feb 19, 2024
| /* If the input is not sorted, bsearch will terminate but with irrelevant results. */ | ||
| static jv f_bsearch(jq_state *jq, jv input, jv target) { | ||
| if (jv_get_kind(input) != JV_KIND_ARRAY) { | ||
| return type_error(input, "cannot be searched from"); |
There was a problem hiding this comment.
Here you are leaking target; you need to free it before returning.
Otherwise looks good to me.
There was a problem hiding this comment.
Maybe also add a test with a non-array input, and a target that uses allocated memory (e.g. a string), so this can be caught by the CI?
|
I just remembered that |
359f0e2
to
2667c55
Compare
emanuele6
reviewed
Feb 29, 2024
emanuele6
reviewed
Feb 29, 2024
2667c55
to
df31443
Compare
This commit fixes issue jqlang#527 and move the bsearch function to a native C-code. The performance is a bit better: Testing script: ```bash clear if [[ `uname` == Darwin ]]; then MAX_MEMORY_UNITS=KB else MAX_MEMORY_UNITS=MB fi export TIMEFMT='%J %U user %S system %P cpu %*E total'$'\n'\ 'avg shared (code): %X KB'$'\n'\ 'avg unshared (data/stack): %D KB'$'\n'\ 'total (sum): %K KB'$'\n'\ 'max memory: %M '$MAX_MEMORY_UNITS''$'\n'\ 'page faults from disk: %F'$'\n'\ 'other page faults: %R' echo "JQ code bsearch" time /usr/bin/jq -n '[range(30000000)] | bsearch(3000)' echo "C code bsearch" time ./jq -n '[range(30000000)] | bsearch(3000)' ```` Results: ``` JQ code bsearch 3000 /usr/bin/jq -n '[range(30000000)] | bsearch(3000)' 8.63s user 0.77s system 98% cpu 9.542 total avg shared (code): 0 KB avg unshared (data/stack): 0 KB total (sum): 0 KB max memory: 823 MB page faults from disk: 1 other page faults: 432828 C code bsearch 3000 ./jq -n '[range(30000000)] | bsearch(3000)' 8.44s user 0.74s system 99% cpu 9.249 total avg shared (code): 0 KB avg unshared (data/stack): 0 KB total (sum): 0 KB max memory: 824 MB page faults from disk: 0 other page faults: 432766 ``` The results may be better if we can use jvp_array_read, and there is no need to copy/free the input array in each iteration. I guess that is like that for API pourposes when the libjq is in use with multiple threads in place. Signed-off-by: Eloy Coto <eloy.coto@acalustra.com>
Co-authored-by: itchyny <itchyny@cybozu.co.jp> Signed-off-by: Eloy Coto <eloy.coto@acalustra.com>
Signed-off-by: Eloy Coto <eloy.coto@acalustra.com>
df31443
to
5c0aaba
Compare
itchyny
approved these changes
Mar 6, 2024
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This commit fixes issue #527 and move the bsearch function to a native C-code.
The performance is a bit better:
Testing script:
Results:
The results may be better if we can use jvp_array_read, and there is no need to copy/free the input array in each iteration. I guess that is like that for API pourposes when the libjq is in use with multiple threads in place.
Closes #527