summaryrefslogtreecommitdiff
path: root/pp_sort.c
Commit message (Collapse)AuthorAgeFilesLines
* Remove the flags OPpSORT_STABLE and OPpSORT_UNSTABLE.Nicholas Clark2021-07-311-8/+0
| | | | | | Remove the code in Perl_ck_sort() that reads from PL_hintgv that sets these, and the code in pp_sort that reads them and sets SORTf_STABLE and SORTf_UNSTABLE (which were no longer read. Remove these too.)
* Rename G_ARRAY to G_LIST; provide back-compat when not(PERL_CORE)Paul "LeoNerd" Evans2021-06-021-1/+1
|
* autodoc.pl: Specify scn for single-purpose filesKarl Williamson2020-11-061-2/+0
| | | | | | | | Many of the files in perl are for one thing only, and hence their embedded documentation will be for that one thing. By creating a hash here of them, those files don't have to worry about what section that documentation goes under, and so it can be completely changed without affecting them.
* Reorganize perlapiKarl Williamson2020-09-041-2/+1
| | | | | This uses a new organization of sections that I came up with. I asked for comments on p5p, but there were none.
* pp_sort.c: silence the "unused parameter" warningTomasz Konojacki2020-03-121-0/+1
| | | | | | | | The 'flags' argument has been unused since 044d25c73ce10d2b29008b875209d414303ccff7 but we can't remove it because it's a public API. Fixes #17632
* optimize sort by inlining comparison functionsTomasz Konojacki2020-03-091-53/+239
| | | | | | | | This makes special-cased forms such as sort { $b <=> $a } even faster. Also, since this commit removes PL_sort_RealCmp, it fixes the issue with nested sort calls mentioned in gh #16129
* pp_sort.c: small refactoringTomasz Konojacki2020-03-091-13/+26
| | | | This will make the future changes a bit easier.
* pp_sort.c: call Perl_sortsv_flags directlyTomasz Konojacki2020-03-091-4/+2
| | | | That pointer isn't needed.
* pp_sort.c: normalize indentationTomasz Konojacki2020-03-091-473/+473
| | | | | | | | According to perlhack, code should be indented with four spaces. This commit doesn't contain any functional changes. If you're seeing it in "git blame" output, try using -w switch, it will hide whitespace-only changes.
* pp_sort.c: remove the remains of quicksortTomasz Konojacki2020-03-021-197/+1
| | | | | e2091bb6ea87111c32936c9170405a44995be338 removed most of it but some dead code remained.
* pp_sort.c: Tinker with pp_sort to untickle mingw bugYves Orton2020-02-041-8/+9
|
* pp_sort.c: fix fencepost error in call to av_extend()Yves Orton2020-01-311-2/+3
| | | | | | | | | | | | | | | | | | | In [rt.cpan.org #39196] issue #17496 there is a report that Tie::File produced spurious blank lines in the file after @tied= sort @tied; it turns out that this is because Tie::File treats EXTEND similarly to STORESIZE (which is arguably not entirely correct, but also not that weird) coupled with an off by one error in the calls to av_extend() in pp_sort. This patch fixes the fencepost error, adds some comments to av_extend() to make it clear what it is doing, and adds a test that EXTEND is called by this code with correct argument.
* perlapi: sortsv_flags is an SV functionKarl Williamson2019-08-091-0/+2
|
* The Windows CE Chainsaw MassacreSteve Hay2019-06-181-5/+0
| | | | | Remove WinCE support as agreed in the thread starting here: https://www.nntp.perl.org/group/perl.perl5.porters/2018/07/msg251683.html
* Revert "Strengthen weak refs when sorting in-place"David Mitchell2018-04-261-3/+0
| | | | | | | | | | | This reverts commit f6107ca24b4cf22dcf7fd69d65612ad718c48fca. See RT #132142. For now, re-introduce the bug that fails to convert weak refs to strong refs when sorting in place. This is commit 2 of 2.
* fix GvSV refcounting in sortZefram2017-12-121-4/+11
| | | | | | | | | | | | | | | Where a sort operation passes the comparands to a comparison block in $a and $b, it wasn't taking account of the fact that the GvSV slots in *a and *b are refcounted. It would write the comparands into those slots without altering any reference counts, and end by restoring the values those slots had to start with. This was all fine so long as nothing else touched those slots during the process. But code running during the comparison is free to write to them by "*a = \1", which does frob the reference counts. Fix it by switching sort to manipulate GvSV in a refcount-preserving manner, compatible with all other operations on those slots. Fixes [perl #92264].
* rip out quicksort and sort algorithm controlZefram2017-11-171-688/+11
| | | | [perl #119635]
* Change save/restore behavior for comparisonsjpl2017-09-211-1/+1
| | | | | | | | S_mergesortsv was saving the current comparison routine only when the SORTf_DESC flag was set, but "restoring" it when ANY flag was set. When some flag other than SORTf_DESC was set, this could lead to the pointer to the comparison routine being set to NULL, triggering a segfault when the routine was subsequently invoked.
* (perl #127663) create a separate random source for internal useTony Cook2017-09-111-1/+1
| | | | | and use it to initialize hash randomization and to innoculate against quadratic behaviour in pp_sort
* Strengthen weak refs when sorting in-placeDagfinn Ilmari Mannsåker2017-09-041-0/+3
| | | | | | It's conceptually an assignment, which should strengthen any weak refs. Reported-by: Tom Molesworth <team@cpan.org>
* Add SORTf_UNSTABLE flagFather Chrysostomos2017-08-211-0/+3
| | | | | | | | This will allow a future commit to make mergesort unstable when the user specifies ‘no sort stable’, since it has been decided that mergesort should remain stable by default. This bit is not yet used, but is quite harmless.
* update size after RenewHugo van der Sanden2017-03-151-1/+1
| | | | | | | | | | | | | | | RT #130841 In general code, change this idiom: PL_foo_max += size; Renew(PL_foo, PL_foo_max, foo_t); to Renew(PL_foo, PL_foo_max + size, foo_t); PL_foo_max += size; so that if Renew dies, PL_foo_max won't be left hanging.
* perlapi.pod: remove AvARRAY() example from sortsv()David Mitchell2017-01-241-4/+3
| | | | | | | | | | The docs for the Perl_sort() API function include a 1-line example of sorting an AV in-place using AvARRAY(av). Since AvARRAY() isn't part of the API and the example would fail on tied or magic arrays, just delete it. At the same time, clarify the docs a bit for Perl_sort() and Perl_sort_flags()
* (perl #130335) fix numeric comparison for sort's built-in compareTony Cook2016-12-231-8/+4
| | | | | | | | | | For non-'use integer' this would always compare as NVs, but with 64-bit integers and non-long doubles, integers can have more significant digits, making the sort <=> replacement less precise than the <=> operator. Use the same code to perform the comparison that <=> does, which happens to be handily broken out into Perl_do_ncmp().
* Change white space to avoid C++ deprecation warningKarl Williamson2016-11-181-1/+1
| | | | | | | | | | | | | | | | | | | | | | C++11 requires space between the end of a string literal and a macro, so that a feature can unambiguously be added to the language. Starting in g++ 6.2, the compiler emits a warning when there isn't a space (presumably so that future versions can support C++11). Unfortunately there are many such instances in the perl core. This commit fixes those, including those in ext/, but individual commits will be used for the other modules, those in dist/ and cpan/. This commit also inserts space at the end of a macro before a string literal, even though that is not deprecated, and removes useless "" literals following a macro (instead of inserting a blank). The result is easier to read, making the macro stand out, and be clearer as to the intention. Code and modules included with the Perl core need to be compilable using C++. This is so that perl can be embedded in C++ programs. (Actually, only the hdr files need to be so compilable, but it would be hard to test that just the hdrs are compilable.) So we need to accommodate changes to the C++ language.
* pp_sort.c: Missing castFather Chrysostomos2016-08-101-1/+1
| | | | This is a compilation error under C++.
* in-place sort preserved element lvalue identityDavid Mitchell2016-08-101-2/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | RT #128340 The in-place sorting optimisation @a = sort @a, was preserving the elements of @a rather than (logically) making copies. So make a copy of any element whose refcount is greater than 1. This may not be the perfect condition, but keeps performance for the common cases. Note that several of the tests in t/op/sort.t actually relied on this behaviour to test whether the sort was being in-placed, so I've added tests for in-placing to t/perf/opcount.t instead. See the previous commit for a general discussion of performance; to the A, B, C in that commit message, here's a fourth column added: D is like C but with this commit added: A B C D ------ ------ ------ ------ Ir 5238.0 2324.0 2772.0 2801.0 Dr 1464.0 649.0 765.0 765.0 Dw 919.0 298.0 370.0 380.0 COND 782.0 320.0 405.0 405.0 IND 25.0 25.0 26.0 26.0 COND_m 14.9 13.0 17.0 17.1 IND_m 8.0 5.0 5.0 5.0 so it has little effect on performance.
* Partially pessimise in-place sortingDavid Mitchell2016-08-101-41/+52
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | There's currently an optimisation that converts at compile-time @a = sort { .... } @a into (approximately) sort { ... } \@a Then at run time, rather than passing an svp pointer to the appropriate sort routine which points to a list of SV*'s on the stack, pp_sort() passes a pointer to @a's AvARRAY. This allows the array to be sorted in-place, which is more efficient. However, it has some issues. First, the @a visible to the sort routine will be varying, whereas logically it should still hold the original list of values until after the '@a = ...' assignment. Secondly, the mergesort algorithm cureently used internally, when in mid-sort, temporarily stores pointers in the array which aren't pointers to SVs - this means that if @a elements are accessed mid-sort, it can crash. The solution to both these problems is for pp_sort() to push the elements of @a onto the stack at the beginning, sort the stack (like normal sorts do), then copy back to @a at the end. This is less efficient than before, but is still a lot more efficient than executing separate padav and aassign ops. Here are benchmark results in raw instruction counts etc (lower is better) for the sort line in this code block: my (@a, @b); @a = reverse 1..10; @b = sort { $a <=> $b } @a; A is for a non-in-place sort, i.e. @b = sort ... @a; B and C are for an inline sort, i.e. as above, but @a = sort ... @a; where B is blead before this commit and C is this commit. A B C ------ ------ ------ Ir 5238.0 2324.0 2772.0 Dr 1464.0 649.0 765.0 Dw 919.0 298.0 370.0 COND 782.0 320.0 405.0 IND 25.0 25.0 26.0 COND_m 14.9 13.0 17.0 IND_m 8.0 5.0 5.0 As can be seen, this partial pessimisation slows down in-place sorting by round 20%, but overall in-place is still nearly twice the speed as without the optimisation. These are the figures for a plain numeric sort (which is optimised to use a C comparison function); for other types of sort, the cost of the comparator dominates, and so the slowdown is much less marked.
* make gimme consistently U8David Mitchell2016-02-031-1/+1
| | | | | | | | | | | | | The value of gimme stored in the context stack is U8. Make all other uses in the main core consistent with this. My primary motivation on this was that the new function cx_pushblock(), which I gave a 'U8 gimme' parameter, was generating warnings where callers were passing I32 gimme vars to it. Rather than play whack-a-mole, it seemed simpler to just uniformly use U8 everywhere. Porting/bench.pl shows a consistent reduction of about 2 instructions on the loop and sub benchmarks, so this change isn't harming performance.
* convert CX_PUSHSUB/POPSUB to inline fnsDavid Mitchell2016-02-031-2/+2
| | | | | | Replace CX_PUSHSUB() with cx_pushsub() etc. No functional changes.
* convert CX_PUSH/POP/TOPBLOCK to inline fnsDavid Mitchell2016-02-031-2/+2
| | | | | | Replace CX_PUSHBLOCK() with cx_pushblock() etc. No functional changes.
* rename PUSHBLOCK,PUSHSUB etc to CX_PUSHBLOCK etcDavid Mitchell2016-02-031-2/+2
| | | | | | | Earlier all the POPFOO macros were renamed to CX_POPFOO to reflect the changed API (like POPBLOCK no longer decremented cxstack_ix). Now rename the PUSH ones for consistency.
* PUSHSUB: make retop a parameterDavid Mitchell2016-02-031-1/+1
| | | | | | Rather than doing cx->blk_sub.retop = NULL in PUSHSUB, then relying on the caller to subsequently change it to something more useful, make it an arg to PUSHSUB.
* PUSHSUB: don't use implicit argsDavid Mitchell2016-02-031-1/+1
| | | | | Make cv and hasargs explicit parameters of PUSHSUB(), rather than just assuming that there are such vars in scope.
* PUSHBLOCK: don't use implicit argsDavid Mitchell2016-02-031-1/+1
| | | | | Make gimme a parameter of PUSHBLOCK() rather than just assuming that there's a 'gimme' var in scope.
* move PL_savestack_ix saving into PUSHBLOCKDavid Mitchell2016-02-031-2/+1
| | | | | | | | | | | | Currently blku_oldsaveix was being set by the various PUSHFOO macros, except for PUSHSUB and PUSHEVAL which expected their caller to do it manually. Now that all the main context state is stored on the context stack rather than than some on the save stack too, things are a lot simpler, and this messy transitional state can now be rationalised, whereby blku_oldsaveix is now always set by PUSHBLOCK; the exact value being specified by a new arg to PUSHBLOCK.
* eliminate PERL_STACK_OVERFLOW_CHECKDavid Mitchell2016-02-031-3/+1
| | | | | | | | This macro is defined as NOOP on all platforms except for MacOS classic, where it was added as a hook to allow for OSes that have a small CPU stack size. Since pp_entersub et al don't actually use the CPU stack, this hook looks misconceived from the beginning. So remove all uses of it in the core.
* sort compare subs: don't do unnecessary scope workDavid Mitchell2016-02-031-15/+3
| | | | | | | | | | | | | | | The 3 functions S_sortcv(), S_sortcv_stacked(), S_sortcv_xsub(), which call a comparison function to compare $a and $b, do unnecessary work with the scope and save stacks. First, they pop any excess scope stack entries; but there shouldn't be, since exiting the sort sub should have already pooped any inner scopes. Indeed, running with an assert that PL_scopestack_ix == oldscopeix didn't trigger any failures. Secondly replace the unconditional leave_scope(oldsaveix) with LEAVE_SCOPE(), which only calls the function if PL_savestack_ix > oldsaveix.
* rename POPFOO() to CX_POPFOO()David Mitchell2016-02-031-2/+2
| | | | | | | | | | | | | | | | Rename all the context-popping macros such as POPBLOCK and POPSUB, by giving them a CX_ prefix. (Do TOPBLOCK too). This is principally to deliberately break any existing non-core use of these non-API macros, as their behaviour has changed in this branch. In particular, POPBLOCK(cx) no longer decrements the cxt stack pointer nor sets cx; instead, cx is now expected to already point to the stack frame which POPBLOCK should process. At the same time, giving them a CX_ prefix makes it clearer that these are all part of a family of macros that manipulate the context stack. The PUSHFOO() macros will be renamed in a later commit.
* add CX_CUR() macroDavid Mitchell2016-02-031-1/+1
| | | | | | This is simply #define CX_CUR() (&cxstack[cxstack_ix])
* move and rename cx_old_savestack_ixDavid Mitchell2016-02-031-1/+1
| | | | | | | | | | | Earlier on in this branch I temporarily added cx_old_savestack_ix as the first element in the context struct. This commit moves it down 32 bits so it now follows type/gimme/u16 in the sbu and blku unions. This means that type is now back as the first item in the struct. I've also renamed it blku_oldsaveix to be more in keeping with similar field names.
* add CX_POP(cx) macro: glorified cxstack_ix--David Mitchell2016-02-031-1/+1
| | | | but with extra checking goodness on debugging builds.
* move blku_old_savestack_ix to base of cxt structDavid Mitchell2016-02-031-1/+1
| | | | | | The previous commit moved the "old savestack" field of substitution contexts into the shared root of the context union. This commit does the same for all other context types
* move CX_LEAVE_SCOPE outside the POPFOO'sDavid Mitchell2016-02-031-3/+3
| | | | | | | | | | Currently every POPFOO macro has CX_LEAVE_SCOPE(cx) as its first action. Since this is common code and not specific to a particular POPFOO type, remove it from each POPFOO macro and make each caller of POPFOO explicitly call CX_LEAVE_SCOPE() instead. This should make no functional difference (but will help if you're single-stepping the code in a debugger :-)
* do PL_tmps_floor save in PUSHBLOCKDavid Mitchell2016-02-031-5/+0
| | | | | | | | | | Currently every individual PUSHFOO type does cx->cx_u.cx_blk.blku_old_tmpsfloor = PL_tmps_floor; PL_tmps_floor = PL_tmps_ix; Move all these into PUSHBLOCK instead, which usually immediately precedes the PUSHFOO.
* do PL_tmps_floor restore in POPBLOCKDavid Mitchell2016-02-031-3/+2
| | | | | | | | | | | Currently every individual POPFOO type does PL_tmps_floor = cx->cx_u.cx_blk.blku_old_tmpsfloor as its last action. Move all these into POPBLOCK instead, which always immediately follows the POPFOO.
* sort(!) out CXt_NULL and CXp_MULTICALLDavid Mitchell2016-02-031-5/+2
| | | | | | | | | | | A sort BLOCK is done using a CXt_NULL context type. Currently it has the CXp_MULTICALL flag set. Remove this flag so that CXp_MULTICALL is only set on CXt_SUB contexts. Also add code comments in various places explainging that CXt_NULL is likely to a sort BLOCK, and fix the comments in pp_return which said a particular code path was only taken by sort BLOCK; it's also taken be (?{...}) too.
* pp_sort: add missing CX_LEAVE_SCOPE()David Mitchell2016-02-031-0/+1
| | | | | | | | | The branch that does POPSUB has an implicit CX_LEAVE_SCOPE; the other branch didn't; do add one for consistency. It's fairly harmless, as pp_sort shortly afterwards does a LEAVE() anyway. Also add an assertion to POPBLOCK that the save stack has been popped; this is how I discovered the sort issue in the first place.
* remove newpm param from POPBLOCK() macro.David Mitchell2016-02-031-1/+1
| | | | | | | Since all core usage of POPBLOCK now immediately restores PL_curpm, there's no need to copy the old value to a temp var specified by the caller; just make POPBLOCK itself restore PL_curpm in the same way that it restores all the other PL_ vars.
* reverse the order of POPBLOCK; POPFOODavid Mitchell2016-02-031-5/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Currently most pp_leavefoo subs have something along the lines of POPBLOCK(cx); POPFOO(cx); where POPBLOCK does cxstack_ix-- and sets cx to point to the top CX stack entry. It then restores a bunch of PL_ vars saved in the CX struct. Then POPFOO does any type-specific restoration, e.g. POPSUB decrements the ref count of the cv that was just executed. However, this is logically the wrong order. When we *enter* a scope, we do PUSHBLOCK; PUSHFOO; so undoing the PUSHBLOCK should be the last thing we do. As it happens, it doesn't really make any difference to the running, which is why we've never fixed it before. Reordering it has two advantages. First, it allows the steps for scope exit to be the exact logical reverse of scope exit, which makes understanding what's going on and debugging easier. It allows us to make the code cleaner. This commit also removes the cxstack_ix-- and setting cx steps from POPBLOCK; now we already expect cx to be set (which it usually already is) and we do the cxstack_ix-- ourselves. This also means we can remove a whole bunch of cxstack_ix++'s that were added immediately after the POPBLOCK in order to prevent the context being inadvertently overwritten before we've finished using it. So in full, POPBLOCK(cx); POPFOO(cx); is now implemented as: cx = &cxstack[cxstack_ix]; ... other stuff done with cx ... POPFOO(cx); POPBLOCK(cx); cxstack_ix--; Finally, this commit also tweaks PL_curcop in pp_leaveeval, since otherwise PL_curcop could temporarily be NULL when debugging code is called in the presence of 'use re Debug'. It also stops the debugging code crashing if PL_curcop is still NULL.
View Lorry Controller Status