difftreelog
perf faster sort
in: master
3 files changed
crates/jrsonnet-evaluator/build.rsdiffbeforeafterboth1use bincode::serialize;2use jrsonnet_parser::{3 parse, Expr, FieldMember, FieldName, LocExpr, Member, ObjBody, ParserSettings,4};5use jrsonnet_stdlib::STDLIB_STR;6use std::{7 env,8 fs::File,9 io::Write,10 path::{Path, PathBuf},11 rc::Rc,12};13use structdump::CodegenResult;1415fn main() {16 let parsed = parse(17 STDLIB_STR,18 &ParserSettings {19 file_name: Rc::new(PathBuf::from("std.jsonnet")),20 loc_data: true,21 },22 )23 .expect("parse");2425 let parsed = if cfg!(feature = "faster") {26 let LocExpr(expr, location) = parsed;27 LocExpr(28 Rc::new(match Rc::try_unwrap(expr).unwrap() {29 Expr::Obj(ObjBody::MemberList(members)) => Expr::Obj(ObjBody::MemberList(30 members31 .into_iter()32 .filter(|p| {33 !matches!(34 p,35 Member::Field(FieldMember {36 name: FieldName::Fixed(name),37 ..38 })39 if **name == *"join" || **name == *"manifestJsonEx" ||40 **name == *"escapeStringJson" || **name == *"equals" ||41 **name == *"base64" || **name == *"foldl" || **name == *"foldr"42 )43 })44 .collect(),45 )),46 _ => panic!("std value should be object"),47 }),48 location,49 )50 } else {51 parsed52 };53 {54 let mut codegen = CodegenResult::default();55 let code = codegen.codegen(&parsed);5657 let out_dir = env::var("OUT_DIR").unwrap();58 let dest_path = Path::new(&out_dir).join("stdlib.rs");59 let mut f = File::create(&dest_path).unwrap();60 f.write_all(&code.as_bytes()).unwrap();61 }62 {63 let out_dir = env::var("OUT_DIR").unwrap();64 let dest_path = Path::new(&out_dir).join("stdlib.bincode");65 let mut f = File::create(&dest_path).unwrap();66 f.write_all(&serialize(&parsed).unwrap()).unwrap();67 }68}crates/jrsonnet-evaluator/src/evaluate.rsdiffbeforeafterboth--- a/crates/jrsonnet-evaluator/src/evaluate.rs
+++ b/crates/jrsonnet-evaluator/src/evaluate.rs
@@ -10,7 +10,7 @@
ForSpecData, IfSpecData, LiteralType, LocExpr, Member, ObjBody, ParamsDesc, UnaryOpType,
Visibility,
};
-use std::{collections::HashMap, rc::Rc};
+use std::{cmp::Ordering, collections::HashMap, rc::Rc};
pub fn evaluate_binding(b: &BindSpec, context_creator: ContextCreator) -> (Rc<str>, LazyBinding) {
let b = b.clone();
@@ -581,6 +581,58 @@
}
Ok(acc)
}))?,
+ // faster
+ ("std", "sortImpl") => noinline!(parse_args!(context, "std.sort", args, 2, [
+ 0, arr: [Val::Arr]!!Val::Arr, vec![ValType::Arr];
+ 1, keyF: [Val::Func]!!Val::Func, vec![ValType::Func];
+ ], {
+ if arr.len() <= 1 {
+ return Ok(Val::Arr(arr))
+ }
+ let mut new_arr = arr.iter().cloned().collect::<Vec<_>>();
+ match keyF.evaluate_values(context.clone(), &[new_arr[0].clone()])? {
+ Val::Str(_) => {
+ let mut err = None;
+ new_arr.sort_by_cached_key(|k| {
+ match keyF.evaluate_values(context.clone(), &[k.clone()]) {
+ Ok(Val::Str(v)) => v,
+ Ok(_) => {
+ err = Some(create_error(crate::error::Error::RuntimeError("types of all array elements should equal".into())));
+ "".into()
+ }
+ Err(e) => {
+ err = Some(e);
+ "".into()
+ }
+ }
+ });
+ if let Some(e) = err {
+ return Err(e);
+ }
+ },
+ Val::Num(_) => {
+ let mut err = None;
+ new_arr.sort_unstable_by(|a, b| {
+ match (keyF.evaluate_values(context.clone(), &[a.clone()]), keyF.evaluate_values(context.clone(), &[b.clone()])) {
+ (Ok(Val::Num(a)), Ok(Val::Num(b))) => a.partial_cmp(&b).unwrap(),
+ (Ok(_a), Ok(_b)) => {
+ err = Some(create_error(crate::error::Error::RuntimeError("types of all array elements should equal".into())));
+ Ordering::Equal
+ }
+ (Err(e), _) | (_, Err(e)) => {
+ err = Some(e);
+ Ordering::Equal
+ }
+ }
+ });
+ if let Some(e) = err {
+ return Err(e);
+ }
+ },
+ _ => return Err(create_error(crate::error::Error::RuntimeError("keys should be number or string".into())))
+ }
+ Ok(Val::Arr(Rc::new(new_arr)))
+ }))?,
("std", "char") => parse_args!(context, "std.char", args, 1, [
0, n: [Val::Num]!!Val::Num, vec![ValType::Num];
], {
crates/jrsonnet-stdlib/src/std.jsonnetdiffbeforeafterboth--- a/crates/jrsonnet-stdlib/src/std.jsonnet
+++ b/crates/jrsonnet-stdlib/src/std.jsonnet
@@ -1131,7 +1131,7 @@
std.makeArray(l, function(i) arr[l - i - 1]),
// Merge-sort for long arrays and naive quicksort for shorter ones
- sort(arr, keyF=id)::
+ sortImpl(arr, keyF)::
local quickSort(arr, keyF=id) =
local l = std.length(arr);
if std.length(arr) <= 1 then
@@ -1166,6 +1166,9 @@
local left = arr[:mid], right = arr[mid:];
merge(std.sort(left, keyF=keyF), std.sort(right, keyF=keyF)),
+ sort(arr, keyF=id)::
+ std.sortImpl(arr, keyF),
+
uniq(arr, keyF=id)::
local f(a, b) =
if std.length(a) == 0 then