C - Is sorting an array of pointers of structs slower than sorting the structs directly (qsort) -


i sorting millions of structs organzied in array qsort-function of standard c library. tried optimize performance creating array of pointers of struct same length. in contrast expectations execution time of second variant slower:

qsort array of structs: 199s qsort array of pointers of structs: 204

i expected time swapping pointer blocks in memory faster moving structs (size 576). may have performance leaks or known behaviour?

there other issues here.

by creating array of pointers fragmenting memory. algorithms in standard libraries designed optimise sorting of contiguous arrays, doing missing cache far more if had bigger array.

quicksort in particular quite locality of reference, halve sample size , sorting subsets of original array in chunks can fit cache.

as general rule, cache misses order of magnitude slower hits. result time delay significant enough make speed not copying bytes.


Comments

Post a Comment

Popular posts from this blog

jOOQ update returning clause with Oracle -

according http://www.jooq.org/doc/3.8/manual/sql-building/sql-statements/update-statement/ jooq doesn't support returning clause in update statements databases except firebird , postgres. does know, still correct oracle jooq? according oracle's documentation, oracle db supports returning clase delete, insert, or update statements. incorrect manual you're right - manual wrong , should fixed: https://github.com/jooq/jooq/issues/5470 single row update returning jooq 3.8 added support single row update .. returning statements. internally, uses callablestatement , pl/sql block of form: begin update "my_table" set "my_table"."column" = 'xyz' "my_table"."id" = 1 returning "my_table"."id", "my_table"."column" ?, ?; ? := sql%rowcount; end; the relevant issue is: https://github.com/jooq/jooq/issues/5190 multi row update returning a...
Read more

java - Warning equals/hashCode on @Data annotation lombok with inheritance -

i have entity inherits other. on other hand, i'm using lombok project reduce boilerplate code, put @data annotation. annotation @data inheritance produces next warning: generating equals/hashcode implementation without call superclass, though class not extend java.lang.object. if intentional, add '@equalsandhashcode(callsuper=false)' type. is advisable add annotation @equalsandhashcode (callsuper = true) or @equalsandhashcode (callsuper = false) ? if not added, 1 callsuper=false or callsuper=true ? the default value false . 1 if don't specify , ignore warning. yes, recommended add @equalsandhashcode annotation on @data annotated classes extend else object. cannot tell if need true or false , depends on class hierarchy, , need examined on case-by-case basis. however, project or package, can configure in lombok.config call super methods if not direct subclass of object. lombok.equalsandhashcode.callsuper = call for configuration system ...
Read more

java - BasicPathUsageException: Cannot join to attribute of basic type -

i using java 8 jpa (hibernate 5.2.1). have clause works perfectly, until introduce clause make use foreign key table values too. i getting following error: basicpathusageexception: cannot join attribute of basic type i think problem related fact have join table, , not sure how create join using join table. employee - employee_category - category model (employee.java): @manytomany(cascade = cascadetype.all, fetch=fetchtype.eager) @jointable ( name="employee_category", joincolumns={ @joincolumn(name="emp_id", referencedcolumnname="id") }, inversejoincolumns={ @joincolumn(name="cat_id", referencedcolumnname="id") } ) private set<category> categories; model (category.java): @id private string id; jpa when introduce following code, fails error above (i think problem new piece of code): join<t, category> category = from.join("id"); predicates.add(criteriabuilder.like(category....
Read more