Meta tags:

Headings (most frequently used words):

big, misconception, is, goto, time, the, sysprof, of, performance, means, about, søren, sandmann, pedersen, first, class, celebrities, die, 7183, at, radix, heap, porter, duff, compositing, and, blend, modes, misconceptions, over, not, translucency, gamma, correction, vs, premultiplied, pixels, fast, multiplication, normalized, 16, bit, numbers, with, sse2, call, cc, in, terms, cooperative, thread, system, average, cluster, size, operations, caching, blending, equals, sign, equality, informally, approximately, equal, statement, worst, case, contact, archive, feeds,

Text of the page (most frequently used words):
the (429), and (127), text (111), that (103), cdot (91), are (63), with (53), this (48), alpha (46), for (44), can (38), will (35), time (34), where (34), because (29), you (28), bucket (28), but (27), both (26), align (26), one (26), from (26), bit (24), not (23), there (23), which (23), more (22), have (22), destination (22), what (21), each (21), than (21), function (21), source (21), lambda (21), then (20), pixels (19), all (19), log (19), item (19), first (18), pixel (18), last_deleted (18), heap (17), new (17), they (17), when (17), over (16), color (16), equal (16), other (16), big (15), here (15), begin (15), end (15), blend (14), also (14), srgb (14), channel (14), operator (14), about (14), items (14), use (13), only (13), displaystyle (13), two (13), region (13), goto (12), case (12), bits (12), linear (12), has (12), number (12), porter (11), duff (11), celebrities (11), read (11), some (11), means (11), between (11), example (11), functions (11), make (11), algorithm (11), comparison (11), callback (11), doesn (10), makes (10), these (10), like (10), background (10), value (10), image (10), would (10), foreground (10), probability (10), worst (10), takes (10), constant (10), being (10), void (10), translucency (9), radix (9), die (9), per (9), another (9), out (9), were (9), enspace (9), must (9), result (9), correct (9), complexity (9), comparisons (9), average (9), redistributed (9), call (9), into (8), way (8), since (8), above (8), simply (8), back (8), right (8), either (8), them (8), done (8), used (8), different (8), mode (8), model (8), mergesort (8), any (8), list (8), buckets (8), size (8), death (8), deaths (8), thread (8), run_list (8), sse2 (7), premultiplied (7), compositing (7), does (7), four (7), look (7), get (7), blending (7), actually (7), frac (7), light (7), sorting (7), based (7), cache (7), set (7), dest (7), blank (7), regions (7), data (7), cluster (7), labels (7), continuation (7), version (6), shorter (6), better (6), computation (6), rgb (6), directly (6), top (6), coverage (6), together (6), sum_ (6), infty (6), reflected (6), now (6), how (6), point (6), algorithms (6), lower (6), theta (6), constants (6), large (6), src (6), table (6), operators (6), present (6), alpha_ (6), extraction (6), next (6), empty (6), celebrity (6), died (6), oort (6), call_cc (6), class (5), full (5), want (5), often (5), format (5), say (5), stored (5), linearly (5), left (5), longer (5), works (5), such (5), see (5), compare (5), three (5), less (5), photon (5), again (5), lets (5), through (5), says (5), type (5), notation (5), sort (5), radixsort (5), keys (5), statement (5), disregarding (5), just (5), write (5), still (5), could (5), images (5), called (5), element (5), highest (5), invariant (5), smaller (5), year (5), defined (5), numbers (4), modes (4), common (4), component (4), else (4), code (4), even (4), 2011 (4), sysprof (4), respectively (4), channels (4), while (4), colors (4), same (4), define (4), similar (4), argument (4), except (4), once (4), partially (4), definition (4), non (4), photoshop (4), someone (4), mean (4), its (4), true (4), expected (4), misconception (4), might (4), however (4), itself (4), concept (4), formula (4), layer (4), visible (4), consider (4), isn (4), integers (4), times (4), follows (4), numbered (4), note (4), minimal (4), structure (4), distribution (4), waiting (4), process (4), period (4), month (4), current (4), calls (4), label (4), structures (4), current_continuation (4), anonymous (4), return (4), age (4), print (4), name (4), foreach (4), methods (4), fast (3), multiplication (3), gamma (3), misconceptions (3), 7183 (3), sandmann (3), second (3), 0x7fff (3), operations (3), though (3), values (3), well (3), known (3), without (3), implement (3), components (3), raised (3), after (3), operation (3), convert (3), raising (3), conversions (3), monitor (3), blended (3), space (3), coded (3), most (3), really (3), useful (3), measure (3), zero (3), exactly (3), assume (3), principle (3), possible (3), passes (3), hits (3), let (3), quicksort (3), statements (3), running (3), behavior (3), byte (3), take (3), primitive (3), many (3), real (3), words (3), fact (3), misses (3), nothing (3), omega (3), informally (3), approximately (3), sufficiently (3), equals (3), sign (3), subseteq (3), hand (3), side (3), formulas (3), general (3), generated (3), various (3), whether (3), twelve (3), layers (3), gimp (3), stopping (3), otherwise (3), according (3), pieces (3), cardboard (3), neither (3), xor (3), filled (3), 2013 (3), tend (3), binary (3), redistribution (3), performance (3), distributed (3), every (3), higher (3), extracted (3), finding (3), find (3), pattern (3), was (3), may (3), poisson (3), variable (3), their (3), child (3), pop_head (3), lexically (3), scoped (3), program (3), jump (3), person_t (3), normalized (2), correction (2), why (2), psrlw (2), pmullw (2), pmulhuw (2), sse (2), registers (2), eight (2), results (2), translation (2), 0xffff (2), int16_t (2), uint16_t (2), psrld (2), paddd (2), 0x8000 (2), punpcklwd (2), direct (2), quickly (2), july (2), release (2), contains (2), texture (2), extensions (2), before (2), final (2), black (2), desired (2), best (2), good (2), much (2), darker (2), display (2), setting (2), those (2), store (2), keeping (2), premultiplication (2), instead (2), divide (2), raise (2), multiply (2), long (2), using (2), human (2), sense (2), computed (2), compute (2), purposes (2), issue (2), opaque (2), masks (2), resulting (2), sum (2), series (2), term (2), reflects (2), towards (2), backside (2), our (2), eyes (2), viewer (2), far (2), along (2), diagram (2), interpreted (2), covers (2), computes (2), amount (2), september (2), 2012 (2), talking (2), depending (2), involved (2), anything (2), string (2), implementation (2), strings (2), everything (2), free (2), implicitly (2), picked (2), apart (2), fine (2), situations (2), always (2), claim (2), usually (2), never (2), misleading (2), topological (2), bound (2), least (2), english (2), becomes (2), precise (2), things (2), easily (2), something (2), seconds (2), runs (2), equality (2), difficult (2), multiplicative (2), additive (2), output (2), chosen (2), gives (2), characterized (2), simple (2), colordodge (2), regular (2), mix (2), equation (2), cases (2), happens (2), places (2), held (2), front (2), shape (2), trimmed (2), despite (2), opacity (2), combine (2), place (2), atop (2), areas (2), given (2), effect (2), march (2), require (2), very (2), miss (2), linked (2), lists (2), line (2), amortized (2), caching (2), added (2), inserting (2), inserted (2), lowest (2), restriction (2), minimum (2), returns (2), highest_bit (2), differs (2), last (2), containing (2), queue (2), restrictions (2), tree (2), exponential (2), events (2), exponentially (2), parameter (2), modelled (2), stochastic (2), suppose (2), rate (2), similarly (2), fixed (2), regularly (2), spaced (2), position (2), jumping (2), exiting (2), thread_yield (2), thread_fork (2), append (2), cooperative (2), system (2), wikipedia (2), resume (2), invoked (2), multiple (2), going (2), feature (2), mindbending (2), passed (2), user (2), person (2), stop (2), iteration (2), method (2), variables (2), arguments (2), nested (2), location (2), returned (2), language (2), off (2), søren (2), pedersen (2), atom, rss, feeds, archive, soren, gmail, com, contact, exercise, work, unfortunately, variants, trick, width, computing, psubw, pcmpgtw, pxor, paddw, avoids, unpacking, 0x0000, matches, packusdw, pmulld, instructions, uses, arithmetic, room, uint32_t, division, 65535, need, candidate, mainly, bug, fixes, samplers, opengl, precisely, filtering, raster, framebuffers, textures, feel, cheating, exponent, become, square, root, sufficient, discarding, displaying, against, worlds, yes, enough, srbg, encoding, too, resolution, lost, tones, converted, manually, video, card, scan, ramp, appropriately, avoided, coding, red, green, blue, expensive, required, happy, discard, graphics, software, perform, half, systems, normally, encoded, allocates, vision, sensitive, historical, accident, nevertheless, remains, reason, relationship, power, august, typical, implementations, select, icons, nautilus, open, tabs, looks, below, selection, rectangle, mouse, problem, dependency, complicated, survives, input, transmitted, argb, shows, sidestepped, assuming, calculations, premultipled, putting, dealing, geometric, compactly, cdots, round, gain, identical, previous, additional, factor, yet, hit, replaced, detail, please, follow, translucent, material, interacts, act, covering, your, tells, fraction, covered, denoted, mask, normal, available, download, stable, randomized, presumably, probably, considered, measuring, imply, pass, reading, shared, bytes, allow, ever, references, lexicographically, goes, sorts, shellsort, bubblesort, comparing, important, applied, underlying, referencing, tell, particular, depend, refers, almost, making, rabbits, island, care, upper, bounds, stricly, greater, types, disposal, come, fewer, translated, severely, toplogical, subset, chances, whoever, said, meant, false, technically, complete, world, bogus, deductions, observation, express, mid, interpret, expression, check, help, found, concerning, total, nonsense, widespread, travestry, face, deduce, positive, seems, people, who, should, know, misunderstand, aspects, following, seen, wild, computer, science, sometimes, mathematics, talk, grows, classifying, abstract, away, differences, computers, october, determined, others, restricted, area, weighted, generalization, rise, contain, corresponding, original, viewed, combinations, involve, tailored, ignore, stack, tailoring, supported, alongside, unlike, substantial, chunk, programs, associated, modify, dodge, conceptually, stacked, stacking, default, composite, referred, shapes, overlay, trim, antialiased, edges, clear, destout, destin, destover, destatop, dst, combination, contents, weights, match, deciding, effects, treated, divided, algebra, equipped, determines, basis, fully, describes, describe, think, irregularly, shaped, colored, glass, generate, insertion, swaps, swap, close, cause, descriptions, recommend, implementing, doubly, mistake, terrible, locality, dynamically, growing, arrays, hot, during, closer, practice, move, life, cycle, single, starts, moves, reaches, maximum, redistributions, experience, dominated, ends, remember, comes, hence, add, determining, instruction, bsr, notice, came, extract, sure, violate, satisfy, old, necessarily, weren, belonged, finally, holds, differing, significant, hypothetical, mentioned, introduction, complement, signed, extracting, involves, walking, deleted, updated, walked, clearly, preserves, didn, change, existing, new_element, bucket_no, ing, adding, 0111, 1101, therefore, belongs, allowed, differ, maintain, global, initially, min_int, severe, heaps, subroutine, dijkstra, shortest, path, prim, spanning, sweepline, computational, geometry, priority, insert, currently, hard, show, infinite, hint, derivative, plugging, third, larger, whose, derived, sim, exp, wait, start, figure, years, worth, randomly, clusters, highlighted, periods, celebrityhood, 12th, rather, trying, constitutes, independently, notwithstanding, intensity, occur, day, music, threes, dismissed, propensity, patterns, none, don, intervals, weird, predictably, 14th, deviate, clustering, inevitable, june, run, support, genericity, somewhat, uglier, demonstrating, create, saves, yields, saving, consists, positions, active, threads, keyword, specifier, process_exit, is_empty, thread_exit, examples, translate, aspect, ness, straightforward, page, jumps, decides, invoke, execution, storing, invoking, semantics, passing, body, expressive, scheme, languages, famous, powerful, packages, part, invocation, terms, older, enclosing, git, solution, throw, exception, little, clumsy, exceptional, situation, defines, prints, declared, syntax, array, inside, unusual, experimental, programming, been, working, mostly, 2007, statically, typed, object, oriented, imperative, classes, arbitrarily, closures, control, usual, ones, etc, 2014,

Text of the page (random words):
r example the color dodge blend mode computes a mix of source and destination according to this formula begin equation b s d begin cases 0 text if d 0 1 text if d ge 1 s d 1 s text otherwise end cases end equation the result is this unlike with the regular over operator in this case there is a substantial chunk of the output where the result is actually a mix of the source and destination layers in photoshop and gimp are not tailored to each other except for layer masks which we will ignore here so the compositing of the layer stack is done with the source only and destination only region set to source and destination respectively however there is nothing in principle stopping us from setting the source only and destination only regions to blank but keeping the blend mode in the both region so that tailoring could be supported alongside blending for example we could set the source region to blank the destination region to the destination color and the both region to colordodge here are the four combinations that involve a colordodge blend mode in this model the original twelve porter duff operators can be viewed as the results of three simple blend modes source b s d s dest b s d d zero b s d 0 in this generalization of porter duff the blend mode is chosen from a large set of formulas and each formula gives rise to four new compositing operators characterized by whether the source and destination are blank or contain the corresponding pixel color here is a table of the operators that are generated by various blend modes the general formula is still an area weighted average a_ text src cdot s a_ text dest cdot d a_ text both cdot b s d where s and d are the source and destination colors respectively or 0 but where b s d is no longer restricted to one of 0 s and d but can instead be chosen from a large set of formulas the output of the alpha channel is the same as before a_ text src cdot text as a_ text dest cdot text ad a_ text both cdot text ab except that ab is now determined by the blend mode for the zero blend mode there is no coverage in the both region so ab is 0 for most others there is full coverage so ab is 1 read more big o misconceptions october 2012 in computer science and sometimes mathematics big o notation is used to talk about how quickly a function grows while disregarding multiplicative and additive constants when classifying algorithms big o notation is useful because it lets us abstract away the differences between real computers as just multiplicative and additive constants big o is not a difficult concept at all but it seems to be common even for people who should know better to misunderstand some aspects of it the following is a list of misconceptions that i have seen in the wild but first a definition we write f n o g n when f n le m g n for sufficiently large n for some positive constant m misconception 1 the equals sign means equality the equals sign in f n o g n is a widespread travestry if you take it at face value you can deduce that since 5 n and 3 n are both equal to o n then 3 n must be equal to 5 n and so 3 5 the expression f n o g n doesn t type check the left hand side is a function the right hand side is a what exactly there is no help to be found in the definition it just says we write without concerning itself with the fact that what we write is total nonsense the way to interpret the right hand side is as a set of functions o f g mid g n le m f n text for some m 0 for large n with this definition the world makes sense again if f n 3 n and g n 5 n then f in o n and g in o n but there is no equality involved so we can t make bogus deductions like 3 5 we can however make the correct observation that o n subseteq o n log n subseteq o n 2 subseteq o n 3 something that would be difficult to express with the equals sign misconception 2 informally big o means approximately equal if an algorithm takes 5 n 2 seconds to complete that algorithm is o n 2 because for the constant m 7 and sufficiently large n 5 n 2 le 7 n 2 but an algorithm that runs in constant time say 3 seconds is also o n 2 because for sufficiently large n 3 le n 2 so informally big o means approximately less than or equal not approximately equal if someone says topological sort like other sorting algorithms is o n log n then that is technically correct but severely misleading because toplogical sort is also o n which is a subset of o n log n chances are whoever said it meant something false if someone says in the worst case any comparison based sorting algorithm must make o n log n comparisons that is not a correct statement translated into english it becomes in the worst case any comparison based sorting algorithm must make fewer than or equal to m n log n comparisons which is not true you can easily come up with a comparison based sorting algorithm that makes more comparisons in the worst case to be precise about these things we have other types of notation at our disposal informally o less than or equal disregarding constants omega greater than or equal disregarding constants o stricly less than disregarding constants theta equal to disregarding constants and some more the correct statement about lower bounds is this in the worst case any comparison based sorting algorithm must make omega n log n comparisons in english that becomes in the worst case any comparison based sorting algorithm must make at least m n log n comparisons which is true and a correct non misleading statement about topological sort is that it is theta n because it has a lower bound of omega n and an upper bound of o n misconception 3 big o is a statement about time big o is used for making statements about functions the functions can measure time or space or cache misses or rabbits on an island or anything or nothing big o notation doesn t care in fact when used for algorithms big o is almost never about time it is about primitive operations when someone says that the time complexity of mergesort is o n log n they usually mean that the number of comparisons that mergesort makes is o n log n that in itself doesn t tell us what the time complexity of any particular mergesort might be because that would depend how much time it takes to make a comparison in other words the o n log n refers to comparisons as the primitive operation the important point here is that when big o is applied to algorithms there is always an underlying model of computation the claim that the time complexity of mergesort is o n log n is implicitly referencing a model of computation where a comparison takes constant time and everything else is free which is fine as far as it goes it lets us compare mergesort to other comparison based sorts such as quicksort or shellsort or bubblesort and in many real situations comparing two sort keys really does take constant time however it doesn t allow us to compare mergesort to radixsort because radixsort is not comparison based it simply doesn t ever make a comparison between two keys so its time complexity in the comparison model is 0 the statement that radixsort is o n implicitly references a model in which the keys can be lexicographically picked apart in constant time which is also fine because in many real situations you actually can do that to compare radixsort to mergesort we must first define a shared model of computation if we are sorting strings that are k bytes long we might take read a byte as a primitive operation that takes constant time with everything else being free in this model mergesort makes o n log n string comparisons each of which makes o k byte comparisons so the time complexity is o k cdot n log n one common implementation of radixsort will make k passes over the n strings with each pass reading one byte and so has time complexity o n k misconception 4 big o is about worst case big o is often used to make statements about functions that measure the worst case behavior of an algorithm but big o notation doesn t imply anything of the sort if someone is talking about the randomized quicksort and says that it is o n log n they presumably mean that its expected running time is o n log n if they say that quicksort is o n 2 they are probably talking about its worst case complexity both statements can be considered true depending on what type of running time the functions involved are measuring read more sysprof 1 2 0 september 2012 a new stable release of sysprof is now available download version 1 2 0 read more over is not translucency september 2011 the porter duff over operator also known as the normal blend mode in photoshop computes the amount of light that is reflected when a pixel partially covers another the fraction of bg that is covered is denoted alpha this operator is the correct one to use when the foreground image is an opaque mask that partially covers the background a photon that hits this image will be reflected back to your eyes by either the foreground or the background but not both for each foreground pixel the alpha value tells us the probability of each a cdot text fg 1 a cdot text bg this is the definition of the porter duff over operator for non premultiplied pixels but if alpha is interpreted as translucency then the over operator is not the correct one to use the over operator will act as if each pixel is partially covering the background which is not how translucency works a translucent material reflects some light and lets other light through the light that is let through is reflected by the background and interacts with the foreground again let s look at this in more detail please follow along in the diagram to the right first with probability a the photon is reflected back towards the viewer displaystyle begin align a cdot text fg end align with probability 1 a it passes through the foreground hits the background and is reflected back out the photon now hits the backside of the foreground pixel with probability 1 a the foreground pixel lets the photon back out to the viewer the result so far displaystyle begin align a cdot text fg 1 a cdot text bg cdot 1 a end align but we are not done yet because with probability a the foreground pixel reflects the photon once again back towards the background pixel there it will be reflected hit the backside of the foreground pixel again which lets it through to our eyes with probability 1 a we get another term where the final 1 a is replaced with a cdot text fg cdot text bg cdot 1 a displaystyle begin align a cdot text fg 1 a cdot text bg cdot 1 a 1 a cdot text bg cdot a cdot text fg cdot text bg cdot 1 a end align and so on in each round we gain another term which is identical to the previous one except that it has an additional a cdot text fg cdot text bg factor displaystyle begin align a cdot text fg 1 a cdot text bg cdot 1 a 1 a cdot text bg cdot a cdot text fg cdot text bg cdot 1 a 1 a cdot text bg cdot a cdot text fg cdot text bg cdot a cdot text fg cdot text bg cdot 1 a cdots end align or more compactly displaystyle begin align a cdot text fg 1 a 2 cdot text bg cdot sum_ i 0 infty a cdot text fg cdot text bg i end align because we are dealing with pixels both a text fg and text bg are less than 1 so the sum is a geometric series displaystyle begin align sum_ i 0 infty x i frac 1 1 x end align putting them together we get displaystyle begin align a cdot text fg frac 1 a 2 cdot bg 1 a cdot text fg cdot text bg end align i have sidestepped the issue of premultiplication by assuming that background alpha is 1 the calculations with premultipled colors are similar and for the color components the result is simply displaystyle begin align r text fg frac 1 a_ text fg 2 cdot text bg 1 text fg cdot text bg end align the issue of destination alpha is more complicated with the over operator both foreground and background are opaque masks so the light that survives both has the same color as the input light with translucency the transmitted light has a different color which means the resulting alpha value must in principle be different for each color component but that s not possible for argb pixels a similar argument to the above shows that the resulting alpha value would be displaystyle begin align r 1 frac 1 a cdot 1 b 1 text fg cdot text bg end align where b is the background alpha the problem is the dependency on text fg and text bg if we simply assume for the purposes of the alpha computation that text fg and text bg are equal to a and b we get this displaystyle begin align r 1 frac 1 a cdot 1 b 1 a cdot b end align which is equal to displaystyle begin align a frac 1 a 2 cdot b 1 a cdot b end align ie exactly the same computation as the one for the color channels so we can define the translucency operator as this displaystyle begin align r text fg frac 1 a 2 cdot text bg 1 text fg cdot text bg end align for all four channels here is an example of what the operator looks like the image below is what you will get if you use the over operator to implement a selection rectangle mouse over to see what it would look like if you used the translucency operator both were computed in linear rgb typical implementations will often compute the over operator in srgb so that s what see if you actually select some icons in nautilus if you want to compare all three open these in tabs over in srgb translucency in linear rgb over in linear rgb and for good measure even though it makes zero sense to do this translucency in srgb read more gamma correction vs premultiplied pixels august 2011 pixels with 8 bits per channel are normally srgb encoded because that allocates more bits to darker colors where human vision is the most sensitive actually it s really more of a historical accident but srgb nevertheless remains useful for this reason the relationship between srgb and linear rgb is that you get an srgb pixel by raising each component of a linear pixel to the power of 1 2 2 it is common for graphics software to perform alpha blending directly on these srgb pixels using alpha values that are linearly coded ie an alpha value of 0 means no coverage 0 5 means half coverage and 1 means full coverage because alpha blending is best done with premultiplied pixels such systems store pixels in this format left alpha enspace alpha cdot text r 1 2 2 enspace alpha cdot text g 1 2 2 enspace alpha cdot text b 1 2 2 right that is the alpha channel is linearly coded while the r g and b channels are first srgb coded then premultiplied with the linear alpha this works well as long as you are happy with blending in srgb and if you discard the alpha channel of such pixels and display them directly on a monitor it will look as if the pixels were alpha blended in srgb space on top of a black background which is the desired result but what if you want to blend in linear rgb if you use the format above some expensive conversions will be required to convert to premultiplied linear you have to first divide by alpha then raise each color to 2 2 then multiply by alpha to convert back you must divi...