git.delta.rocks / jrsonnet / refs/commits / 226d3aa6c541

difftreelog

perf faster sort

Лач2020-07-19parent: #34b1225.patch.diff
in: master

3 files changed

modifiedcrates/jrsonnet-evaluator/build.rsdiffbeforeafterboth
before · crates/jrsonnet-evaluator/build.rs
1use 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}
after · crates/jrsonnet-evaluator/build.rs
1use 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								**name == *"sortImpl"43							)44						})45						.collect(),46				)),47				_ => panic!("std value should be object"),48			}),49			location,50		)51	} else {52		parsed53	};54	{55		let mut codegen = CodegenResult::default();56		let code = codegen.codegen(&parsed);5758		let out_dir = env::var("OUT_DIR").unwrap();59		let dest_path = Path::new(&out_dir).join("stdlib.rs");60		let mut f = File::create(&dest_path).unwrap();61		f.write_all(&code.as_bytes()).unwrap();62	}63	{64		let out_dir = env::var("OUT_DIR").unwrap();65		let dest_path = Path::new(&out_dir).join("stdlib.bincode");66		let mut f = File::create(&dest_path).unwrap();67		f.write_all(&serialize(&parsed).unwrap()).unwrap();68	}69}
modifiedcrates/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];
 			], {
modifiedcrates/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