It's better than C++ where you cast a pointer and the code happily treats random gibberish as the type you cast to.
Funny that you mention C++ instead of C for this argument. In C, pretty much all you can do is cast the pointer and cross your fingers. In C++, you can correctly handle run-time polymorphism with dynamic_cast (or just use a virtual function to begin with, dynamic casting is usually a code-smell); or you can handle compile-time polymorphism with templates which rely on more-or-less the same duck typing that Python does. The compile-time polymorphism is admittedly much hairier (cryptic syntax, potential surprises from ADL/Koenig lookup, and some nastiness with function overloading vs. template specialization), but your characterization of C++ sounds like a straw man borne out of some unnecessarily bad programming experience.
I believe the GP is referring to how variables are referenced from within the program. Consider the code import re; re.compile("...") (and sorry in advance if I miss any gritty details): the re.compile lookup first searches for "re" in the local and global symbol dictionaries, then once it finds one it searches for "compile" within that dictionary, then it searches for "__call__" within that dictionary, then it invokes the result as a function. So in that sense, the language is dictionaries all the way down. It also means that you can micro-optimize python code by creating local references to deeply.nested.things.in.modules to avoid doing the entire lookup chain in a tight loop.
Contrast this with dynamically-linked executables (e.g. C-family and probably anything else that requires a linker), where only undefined functions/variables are strings that need to be looked up in a symbol table. In this system there is one symbol dictionary per executable/shared-library, and any run-time name lookups occur on first load or first use. All other function and variable references are resolved into addresses at compile- or link-time.
if you're skilled enough to write optimized code in C/C++, why fuck around with Python at all?
Because Python is superior for prototyping an algorithm. As a skilled C++ programmer, I still recognize that it takes time to optimize and it's only worthwhile if the architecture is appropriate (solves the right problems, handles all edge cases and dark corners, uses appropriate data structures and algorithms). If I can bang out a Python implementation that does the right job slowly, the translation to a high-bandwidth or low-latency C++ implementation is usually a breeze.
Consequently most non-specialist programmers, even those who have done plenty of assembly work in their time, would produce slower final code today by hand-crafting their own assembly language than they would by writing in C and verifying the output of a good compiler to take care of the code generation.
For the most part, the compiler kicks my ass at generating assembly. But every once in a while I find that I have programmed some construct that it's not very good at optimizing, or I've subtly surpassed some parametrized limit after which the compiler decides to stop optimizing. Or maybe I've forgotten to give the compiler the right hints for function visibility, pointer aliasing, or the like. Or heck, maybe I am making some meatspace assumptions that the compiler is not at liberty to make, and I need to find a way to codify the assumptions.
In any case, I agree with you that the solution is almost always "tweak the high-level code until the compiler groks me" and not "discard the compiler and write some assembler"; but I find that the "blind trust" approach to compiler-assisted optimization leads falls apart pretty quickly. Always verify!
They do a lot of really neat stuff with Operating systems and programing languages.
They also do some interesting graphics-related research. Off the top of my head, I remember some work on procedural texture generation and progressive mesh simplification.
what's wrong with the "The Chicago Way" style of corruption?
The lifespan of any given section of I-88, for one. I am not a civil engineer, but I hear that major roads can be built for much more longevity than I see here. It may be cheaper in the short term, but frequent summer construction really sucks, and someone with a more statistical bent than me could probably put a pretty large number on the man-hours lost in traffic.
Also, your cost analysis assumes that corruption only factors into contractor selection. Corruption also dictates which projects even get executed. For example, see the demolition of Meigs Field. This was done precisely to circumvent The Process (between Chicago, Illinois, and the FAA) and complete one of his pet projects.
Eccentricity of the lunar orbit only comprises a difference of about 42,000 km.... or.14 light-seconds. 140 milliseconds of latency difference between apogee and perigee.
We're talking, of course, about Earth's second moon. You know, the one with a 3600-year elliptical orbit where The Gods live. It must be their children sending these pulses of light at us, the way an Earthling child aims a laser pointer at an airplane.
I compiled two versions using gcc-4.4 on an Intel i7 chipset (this version actually targets core2 instruction latencies, but it's close enough for my purpose). Compile/link lines:
There are only a few salient differences in the optimized build: the first is a smaller stack size (0x8 bytes instead of 0x88). This probably doesn't have much impact on caching (there aren't many function calls, and none in the critical path), but it does mean that more variables are going through unnecessary load/store cycles. The second is that the optimized build issued roughly half of the function calls. Any functions in the computation kernel count as trimmable fat. The final difference is that the native-tuned build frequently used conditional-move operations. This reduces pressure on branch prediction hardware.
I benchmarked both using a single series of calls in the sequence 1, 2, 5, 10, 20, 50, 100, 200, 500,..., 5000000. Due to impatience I did not go all the way out to 20M as you suggest, but the results to 5M already show a smooth geometric scale that I expect would continue until I run out of main memory. I used getrusage() to track various runtime statistics and saw the following:
findprimes0: cpu time (utime) ~72 seconds, involuntary context switches (nivcsw) ~80.
findprimes3: utime ~50 seconds, nivcsv ~60.
Overall, I hope that this convinces you that compiler optimization flags matter across the board for C++. I believe this is one of the downsides of C and C++ as a mainstream application language: optimization for the target runtime environment is required by application developers. That being said, this problem is very light on the CPU and very heavy on memory bandwidth, so I suspect that any implementation could be optimized substantially by parallelizing the sieve checks. Consider that for any given value N above some small absolute value, it should be guaranteed that N-1, N-2,..., N-K are all relatively prime. Thus, the algorithm should be able to batch-process chunks of N values against the list of existing primes in parallel. This is essentially a manual loop-unrolling, but it relies on information that we only know from mathematical proof (i.e. no modern compiler or runtime could be expected to perform this optimization automatically).
Speed limits recommended by people smarter than you are about the subject at hand and then set by lawmakers.
FTFY. The safety engineers don't directly set the speed limits in any case that I have heard of. Lawmakers setting speed limits may arbitrarily limit it based on public perception (to appear "tough on safety") or to meet the standards set by a larger funding body (almost all state DOTs who receive federal funding). To assume that the legal limit is somehow a magical moral barrier is to put more trust in the local authority than you probably should.
Community service is an immediate effective penalty that can be verified.
The other nice thing about community service is that "time served" is comparable regardless of income and social stature. You'll never hear about "free time disparity" between high-falutin' CEOs and blue-collar workers the way you do with income inequality. Maybe you could argue that it is biased in favor of the "permanently/habitually unemployed"; but the again, time is the best resource they could be asked to give!
Speaking as someone who regularly looks at the assembler output of gcc, it sure as heck does.
You can't unroll the loops on this one. So even the basic optimization cannot be done.
Loop unrolling doesn't happen until -O3, and even then it's not a clear-cut optimization because it bloats the instruction stream and potentially confuses the hardware branch predictors (which are—as one might expect—optimized for loops). There are plenty of other optimization passes that the compiler can go through. To name a few:
tail recursion to eliminate stack growth
better register allocation to reduce (or eliminate) stack usage
static branch prediction to reduce the likelihood stalls from conditionals
instruction reordering to reduce the impact of stalls from conditionals or execution-unit bandwidth
The hardware should be irrelevant. I ran both the java version and the g++ version on the same box under the same operating system.
GCC by default targets the generic architecture (there's a way to tell if the version you're using targets something else, but sorry, I forget at the moment). This means it won't use any of the newer x86 or x86_64 instructions. It also limits the compiler's knowledge about instruction latencies, and branch penalties, and the cache hierarchy. It is likely that you penalized the C++ version simply because Java is designed to abstract these details into the jvm itself.
If you're kind (and organized) enough to be able to provide me with the original code and command-line arguments, I can take a crack at some basic compiler-flag tweaking and get back to you about experimental difference.
You are mistaking debugging information with optimization levels. It's unlikely that you had a legitimate comparison. For starters, what compiler/version did you use? What other options besides -g were used? What hardware was used?
They usually decompose it down to Infoset, and then store that in some relational fashion with indexes and stuff; and reconstute XML when returning results of a query.
All of that processing and reconstitution really destroys the nutritional value, and excess compression contributes to high 0x80 levels. You really should be mindful about the data that you are putting into your program.
The repetition of "duck" makes the URL pretty annoying to type as well. At they very least, they can get a shorter domain that's easy to remember!
You only need to type the URL once, to get to the front page. Then right-click the text box, select "create search", and follow the defaults. At least, this works for Opera; for Firefox and IE the functionality is the same but YMMV on the UI. The real beauty is that I can use the bang syntax to get results from other popular search engines, so DDG becomes the default search engine to maximize convenience. Even the Berkeley man-pages (!man).
Also, it may be a cultural thing, but I find "duck-duck-go" very easy to say. It sounds like a common (American?) childhood game, duck-duck-goose, which makes it easy to latch onto despite the length.
in general technical people do not like overloading
I agree with your sentiment wholeheartedly: precision in language and conversation is important.
Compression in computing already has a very specific meaning (it's a stream operation)
Compression is an aspect of Information Theory or Entropy. From this perspective, it is the reduction of redundant bits of information in a given corpus (which is usually a stream because that's natural, but I don't know that there is an inherent requirement). All software which compresses data does so by finding and eliminating duplicate chunks of bits. The term "data deduplication" seems to have arisen in the tech industry to refer to compression algorithms on filesystems which use very large chunks of bits (files/blocks) compared to prior tools. But that's really just a marketing label. It's still a reduction in redundant bits of information stored, ergo it is still compression. The "technical people" in this conversation—Information Theorists—will see that deduplication:compression::square:shape, and no overloading has occurred.
if we lived in an inconsistent universe there would be no "truth" to speak of -- things would be true and false at the same time, and any claim that could be made would be true.
NASDAQ used to offer several intraday auctions, which AFAIK amount to the same thing (but on a different timescale... maybe every 2 hours?) I don't know why they got rid of them, but it's worth investigating if you are interested in essentially reviving the practice.
The stock market, however, is not meant to be a casino.
Really? If you're thinking of the same stock market as I am, it's hard to believe that it's not intended to be a casino.
The justification for its existence and for treating it like something other than a gambling parlour is that it's a system for providing capital for companies.
Capital comes to companies through IPOs and corporate bond issuances. The stock market that you hear about on a daily basis is almost entirely the secondary market, which is a big pool of speculators (of varying lengths of time... but indeed everyone is speculating that the company won't go bankrupt) whose only "purpose" from a market perspective is to lend confidence to IPOs. The real problem as I see it is that the general public is led to believe that the stock market should be important in their daily life. It shouldn't, precisely because it is so volatile and whimsical.
HFT only provides the illusion of liquidity in one direction--that which the stock is moving in.
You're thinking of aggressive HFT strategies. The other side is maker makers. The market makers that have not adopted low-latency technology have probably gotten cooked by the HFT aggressors already (or they have some cozy regulatory edge). Thus, it is logical to assume that most modern market makers are also HFT, and they do provide liquidity against momentum. But in a case like the flash crash, of course they all pulled out. Nobody deliberately stands in front of a train.
That is illegal, and it requires the HFTrader to be a broker with access to customer orders. If you think your broker is front-running you, you must assume they are profiting off of it. If they are profiting off of it, then surely you can demonstrate that by looking at your own execution quality vs. the market. Oh, and any prop shop with no customer orders? By definition, they are not front-running anyone.
kick stops,
Triggering stop orders requires pushing the price around, which requires capital in order to take on large positions. HFT is not very capital-intensive because it doesn't involve large positions. This is more likely to be a different set of traders, and they've surely been around the block a lot longer than any modern HFT shops.
stuff quotes and so on.
Yep, HFTraders can do this. It's pretty shitty, I agree. It should also be very easy to identify after the fact, but since I haven't heard very much about enforcement on quote-stuffing I can only assume that either it isn't a chronic problem or that the appropriate regulatory body (SEC for US stocks) doesn't care.
Slashdot Mirror
Funny that you mention C++ instead of C for this argument. In C, pretty much all you can do is cast the pointer and cross your fingers. In C++, you can correctly handle run-time polymorphism with dynamic_cast (or just use a virtual function to begin with, dynamic casting is usually a code-smell); or you can handle compile-time polymorphism with templates which rely on more-or-less the same duck typing that Python does. The compile-time polymorphism is admittedly much hairier (cryptic syntax, potential surprises from ADL/Koenig lookup, and some nastiness with function overloading vs. template specialization), but your characterization of C++ sounds like a straw man borne out of some unnecessarily bad programming experience.
I believe the GP is referring to how variables are referenced from within the program. Consider the code import re; re.compile("...") (and sorry in advance if I miss any gritty details): the re.compile lookup first searches for "re" in the local and global symbol dictionaries, then once it finds one it searches for "compile" within that dictionary, then it searches for "__call__" within that dictionary, then it invokes the result as a function. So in that sense, the language is dictionaries all the way down. It also means that you can micro-optimize python code by creating local references to deeply.nested.things.in.modules to avoid doing the entire lookup chain in a tight loop.
Contrast this with dynamically-linked executables (e.g. C-family and probably anything else that requires a linker), where only undefined functions/variables are strings that need to be looked up in a symbol table. In this system there is one symbol dictionary per executable/shared-library, and any run-time name lookups occur on first load or first use. All other function and variable references are resolved into addresses at compile- or link-time.
Because Python is superior for prototyping an algorithm. As a skilled C++ programmer, I still recognize that it takes time to optimize and it's only worthwhile if the architecture is appropriate (solves the right problems, handles all edge cases and dark corners, uses appropriate data structures and algorithms). If I can bang out a Python implementation that does the right job slowly, the translation to a high-bandwidth or low-latency C++ implementation is usually a breeze.
For the most part, the compiler kicks my ass at generating assembly. But every once in a while I find that I have programmed some construct that it's not very good at optimizing, or I've subtly surpassed some parametrized limit after which the compiler decides to stop optimizing. Or maybe I've forgotten to give the compiler the right hints for function visibility, pointer aliasing, or the like. Or heck, maybe I am making some meatspace assumptions that the compiler is not at liberty to make, and I need to find a way to codify the assumptions.
In any case, I agree with you that the solution is almost always "tweak the high-level code until the compiler groks me" and not "discard the compiler and write some assembler"; but I find that the "blind trust" approach to compiler-assisted optimization leads falls apart pretty quickly. Always verify!
They also do some interesting graphics-related research. Off the top of my head, I remember some work on procedural texture generation and progressive mesh simplification.
UIUC's per-student tuition would skyrocket (Chicagoland no longer being in-state), or the incoming student population would plummet.
It's so fitting that Chicago got to be Gotham City. I wonder if Christopher Nolan was trying to send a message...
The lifespan of any given section of I-88, for one. I am not a civil engineer, but I hear that major roads can be built for much more longevity than I see here. It may be cheaper in the short term, but frequent summer construction really sucks, and someone with a more statistical bent than me could probably put a pretty large number on the man-hours lost in traffic.
Also, your cost analysis assumes that corruption only factors into contractor selection. Corruption also dictates which projects even get executed. For example, see the demolition of Meigs Field. This was done precisely to circumvent The Process (between Chicago, Illinois, and the FAA) and complete one of his pet projects.
We're talking, of course, about Earth's second moon. You know, the one with a 3600-year elliptical orbit where The Gods live. It must be their children sending these pulses of light at us, the way an Earthling child aims a laser pointer at an airplane.
I compiled two versions using gcc-4.4 on an Intel i7 chipset (this version actually targets core2 instruction latencies, but it's close enough for my purpose). Compile/link lines:
There are only a few salient differences in the optimized build: the first is a smaller stack size (0x8 bytes instead of 0x88). This probably doesn't have much impact on caching (there aren't many function calls, and none in the critical path), but it does mean that more variables are going through unnecessary load/store cycles. The second is that the optimized build issued roughly half of the function calls. Any functions in the computation kernel count as trimmable fat. The final difference is that the native-tuned build frequently used conditional-move operations. This reduces pressure on branch prediction hardware.
I benchmarked both using a single series of calls in the sequence 1, 2, 5, 10, 20, 50, 100, 200, 500, ..., 5000000. Due to impatience I did not go all the way out to 20M as you suggest, but the results to 5M already show a smooth geometric scale that I expect would continue until I run out of main memory. I used getrusage() to track various runtime statistics and saw the following:
common: physical memory (maxrss) 77K, page faults (minflt) 35K
findprimes0: cpu time (utime) ~72 seconds, involuntary context switches (nivcsw) ~80.
findprimes3: utime ~50 seconds, nivcsv ~60.
Overall, I hope that this convinces you that compiler optimization flags matter across the board for C++. I believe this is one of the downsides of C and C++ as a mainstream application language: optimization for the target runtime environment is required by application developers. That being said, this problem is very light on the CPU and very heavy on memory bandwidth, so I suspect that any implementation could be optimized substantially by parallelizing the sieve checks. Consider that for any given value N above some small absolute value, it should be guaranteed that N-1, N-2, ..., N-K are all relatively prime. Thus, the algorithm should be able to batch-process chunks of N values against the list of existing primes in parallel. This is essentially a manual loop-unrolling, but it relies on information that we only know from mathematical proof (i.e. no modern compiler or runtime could be expected to perform this optimization automatically).
FTFY. The safety engineers don't directly set the speed limits in any case that I have heard of. Lawmakers setting speed limits may arbitrarily limit it based on public perception (to appear "tough on safety") or to meet the standards set by a larger funding body (almost all state DOTs who receive federal funding). To assume that the legal limit is somehow a magical moral barrier is to put more trust in the local authority than you probably should.
The other nice thing about community service is that "time served" is comparable regardless of income and social stature. You'll never hear about "free time disparity" between high-falutin' CEOs and blue-collar workers the way you do with income inequality. Maybe you could argue that it is biased in favor of the "permanently/habitually unemployed"; but the again, time is the best resource they could be asked to give!
Speaking as someone who regularly looks at the assembler output of gcc, it sure as heck does.
Loop unrolling doesn't happen until -O3, and even then it's not a clear-cut optimization because it bloats the instruction stream and potentially confuses the hardware branch predictors (which are—as one might expect—optimized for loops). There are plenty of other optimization passes that the compiler can go through. To name a few:
GCC by default targets the generic architecture (there's a way to tell if the version you're using targets something else, but sorry, I forget at the moment). This means it won't use any of the newer x86 or x86_64 instructions. It also limits the compiler's knowledge about instruction latencies, and branch penalties, and the cache hierarchy. It is likely that you penalized the C++ version simply because Java is designed to abstract these details into the jvm itself.
If you're kind (and organized) enough to be able to provide me with the original code and command-line arguments, I can take a crack at some basic compiler-flag tweaking and get back to you about experimental difference.
You are mistaking debugging information with optimization levels. It's unlikely that you had a legitimate comparison. For starters, what compiler/version did you use? What other options besides -g were used? What hardware was used?
All of that processing and reconstitution really destroys the nutritional value, and excess compression contributes to high 0x80 levels. You really should be mindful about the data that you are putting into your program.
You only need to type the URL once, to get to the front page. Then right-click the text box, select "create search", and follow the defaults. At least, this works for Opera; for Firefox and IE the functionality is the same but YMMV on the UI. The real beauty is that I can use the bang syntax to get results from other popular search engines, so DDG becomes the default search engine to maximize convenience. Even the Berkeley man-pages (!man).
Also, it may be a cultural thing, but I find "duck-duck-go" very easy to say. It sounds like a common (American?) childhood game, duck-duck-goose, which makes it easy to latch onto despite the length.
I agree with your sentiment wholeheartedly: precision in language and conversation is important.
Compression is an aspect of Information Theory or Entropy. From this perspective, it is the reduction of redundant bits of information in a given corpus (which is usually a stream because that's natural, but I don't know that there is an inherent requirement). All software which compresses data does so by finding and eliminating duplicate chunks of bits. The term "data deduplication" seems to have arisen in the tech industry to refer to compression algorithms on filesystems which use very large chunks of bits (files/blocks) compared to prior tools. But that's really just a marketing label. It's still a reduction in redundant bits of information stored, ergo it is still compression. The "technical people" in this conversation—Information Theorists—will see that deduplication:compression::square:shape, and no overloading has occurred.
In short, don't diss your roots.
Really??? I love Discworld!
Wow, I hope you have a good THAC0!
Deduplication is compression.
Yes, and the stench is terrible if you pee on either of them.
NASDAQ used to offer several intraday auctions, which AFAIK amount to the same thing (but on a different timescale... maybe every 2 hours?) I don't know why they got rid of them, but it's worth investigating if you are interested in essentially reviving the practice.
Really? If you're thinking of the same stock market as I am, it's hard to believe that it's not intended to be a casino.
Capital comes to companies through IPOs and corporate bond issuances. The stock market that you hear about on a daily basis is almost entirely the secondary market, which is a big pool of speculators (of varying lengths of time... but indeed everyone is speculating that the company won't go bankrupt) whose only "purpose" from a market perspective is to lend confidence to IPOs. The real problem as I see it is that the general public is led to believe that the stock market should be important in their daily life. It shouldn't, precisely because it is so volatile and whimsical.
You're thinking of aggressive HFT strategies. The other side is maker makers. The market makers that have not adopted low-latency technology have probably gotten cooked by the HFT aggressors already (or they have some cozy regulatory edge). Thus, it is logical to assume that most modern market makers are also HFT, and they do provide liquidity against momentum. But in a case like the flash crash, of course they all pulled out. Nobody deliberately stands in front of a train.
That is illegal, and it requires the HFTrader to be a broker with access to customer orders. If you think your broker is front-running you, you must assume they are profiting off of it. If they are profiting off of it, then surely you can demonstrate that by looking at your own execution quality vs. the market. Oh, and any prop shop with no customer orders? By definition, they are not front-running anyone.
Triggering stop orders requires pushing the price around, which requires capital in order to take on large positions. HFT is not very capital-intensive because it doesn't involve large positions. This is more likely to be a different set of traders, and they've surely been around the block a lot longer than any modern HFT shops.
Yep, HFTraders can do this. It's pretty shitty, I agree. It should also be very easy to identify after the fact, but since I haven't heard very much about enforcement on quote-stuffing I can only assume that either it isn't a chronic problem or that the appropriate regulatory body (SEC for US stocks) doesn't care.